QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#810388 | #8236. Snake Move | bitwim | RE | 1ms | 7660kb | C++14 | 2.1kb | 2024-12-11 21:53:46 | 2024-12-11 21:53:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[3010][3010];
int f[3010][3010];
const array<int, 2> mov[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int ans = 0;
void solve() {
int n, m, k;
cin >> n >> m >> k;
int x, y;
cin >> x >> y;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
a[i][j] = 0;
f[i][j] = -1;
}
}
int ans = 0;
for(int i = 2; i <= k; ++i) {
int x1, y1;
cin >> x1 >> y1;
a[x1][y1] = k - i;
}
char c;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin >> c;
if(c == '#') {
// cerr << 1 << '\n';
a[i][j] = -1;
}
// cout << a[i][j] << ' ';
}
// cout << '\n';
}
f[x][y] = 0;
queue<pair<int, int>> q;
q.push({x, y});
int time = 0;
while(!q.empty()) {
++time;
auto now = q.front();
q.pop();
// cerr << 1 << '\n';
int val = f[now.first][now.second];
for(int i = 0; i < 4; ++i) {
int nx = now.first + mov[i][0];
int ny = now.second + mov[i][1];
if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
if(a[nx][ny] == -1) continue;
if(f[nx][ny] == -1 || f[nx][ny] > max(val + 1, a[nx][ny] + 1)) {
f[nx][ny] = max(val + 1, a[nx][ny] + 1);
q.push({nx, ny});
}
}
assert(time < 2000000);
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
// cout << f[i][j] << ' ';
if(f[i][j] != -1) {
ans += f[i][j] * f[i][j];
}
}
// cout << '\n';
}
cout << ans << '\n';
}
signed main() {
// cout<<fixed<<setprecision(12);
// cerr << mul()
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
// int t;
// cin >> t;
// while(t--) {
// solve();
// }
solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7660kb
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: 1ms
memory: 5612kb
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: 1ms
memory: 5616kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: -100
Runtime Error
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................