QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#587135 | #8236. Snake Move | SLF666# | WA | 663ms | 154680kb | C++17 | 1.9kb | 2024-09-24 17:44:34 | 2024-09-24 17:44:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
//#define int ull
#define endl "\n"
int nt[4][2] = {
{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
void solve(){
ull n, m, k;
cin >> n >> m >> k;
map<pair<int, int>, ull> mp;
int i;
int nowx1 = -1, nowy1 = -1;
int nowx2 = -1, nowy2 = -1;
for(i = 0 ; i < k ; i ++) {
int x, y;
cin >> x >> y;
x--;
y--;
if(i == 0) {
nowx1 = x;
nowy1 = y;
}
if(i == 1) {
nowx2 = x;
nowy2 = y;
}
if(i != 0) mp[{x, y}] = k - i;
}
vector<vector<ull>> f1(n + 3, vector<ull>(m + 3, 1e18));
vector<vector<ull>> book(n + 3, vector<ull>(m + 3, 0));
vector<string> a(n + 3);
int j;
for(i = 0 ; i < n ; i ++) {
cin >> a[i];
}
queue<pair<ull, pair<int, int>>> q;
// priority_queue<pair<ull, pair<int, int>>, vector<pair<ull, pair<int, int>>>, greater<pair<ull, pair<int, int>>> > q;
q.push({0, {nowx1, nowy1}});
while(!q.empty()) {
auto it = q.front();
q.pop();
int x = it.second.first;
int y = it.second.second;
ull step = it.first;
if(x < 0 || y < 0 || x >= n || y >= m) continue;
if(a[x][y] == '#') continue;
f1[x][y] = min(f1[x][y], step);
if(mp.count({x, y})) {
f1[x][y] = max(mp[{x, y}], f1[x][y]);
}
if(book[x][y]) continue;
book[x][y] = 1;
for(i = 0 ; i < 4 ; i ++) {
int nx = x + nt[i][0], ny = y + nt[i][1];
int ss = f1[x][y] + 1;
q.push({ss, {nx, ny}});
}
}
for(i = 0 ; i <= n ; i ++) {
for(j = 0 ; j <= m ; j ++) book[i][j] = 0;
}
ull ans = 0;
for(i = 0 ; i < n ; i ++) {
for(j = 0 ; j < m ; j ++) {
if(f1[i][j] == 1e18) continue;
ans += f1[i][j] * f1[i][j];
// cout << f1[i][j] << ' ';
}
// cout << endl;
}
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....
output:
293
result:
ok single line: '293'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
2 2 4 1 1 1 2 2 2 2 1 .. ..
output:
14
result:
ok single line: '14'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 587ms
memory: 149920kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 609ms
memory: 149556kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 35ms
memory: 154048kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 35ms
memory: 149092kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 636ms
memory: 149876kb
input:
2900 3000 10 2883 1758 2883 1759 2883 1760 2883 1761 2883 1762 2884 1762 2884 1763 2883 1763 2882 1763 2882 1764 ........................................................#............................#........................................................................................................
output:
49803365625286
result:
ok single line: '49803365625286'
Test #9:
score: -100
Wrong Answer
time: 663ms
memory: 154680kb
input:
3000 3000 10 2015 1932 2015 1931 2015 1930 2015 1929 2016 1929 2017 1929 2018 1929 2018 1928 2018 1927 2017 1927 #...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......
output:
22509095749317
result:
wrong answer 1st lines differ - expected: '22509095749285', found: '22509095749317'