QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#692747 | #8236. Snake Move | CMing | RE | 0ms | 3828kb | C++17 | 2.3kb | 2024-10-31 14:58:54 | 2024-10-31 14:58:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 10;
int g[N][N];
int f[N][N];
// 上、下、左、右
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const int inf = 1e9;
struct node
{
int x, y;
int d;
};
int n, m, k;
bool check(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void bfs(int sx, int sy, int _d)
{
f[sx][sy] = 0;
queue<node> q;
q.push({sx, sy, _d});
while(q.size())
{
auto [x, y, d] = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int tx = x + dir[i][0], ty = y + dir[i][1];
if(!check(tx, ty)) continue;
if(g[tx][ty] == -1) continue;
// if(i == (d ^ 1))
// {
// f[tx][ty] = f[x][y] + k - g[tx][ty]
// }
if(f[x][y] + 1 < f[tx][ty])
{
int dis = f[x][y] + 1;
if(g[tx][ty] > 0) dis = max(dis + max(k - g[tx][ty] - f[x][y], 0), k - g[tx][ty]);
f[tx][ty] = dis;
q.push({tx, ty, i});
}
}
}
}
signed main()
{
cin >> n >> m >> k;
int sx, sy;
int d = -1;
for(int i = 1; i <= k; i++)
{
int x, y; cin >> x >> y;
if(i == 1) sx = x, sy = y;
if(i == 2)
{
if(x == sx)
{
if(y < sy) d = 3;
else d = 2;
}
else if(x < sx) d = 1;
else d = 0;
}
g[x][y] = i;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
f[i][j] = inf;
char t; cin >> t;
if(g[i][j]) continue;
g[i][j] = (t == '#') ? -1 : 0;
}
// for(int i = 1; i <= n; i++)
// {
// for(int j = 1; j <= m; j++)
// cout << g[i][j] << " ";
// cout << "\n";
// }
// cout<<"\n-----------\n";
bfs(sx, sy, d);
ULL ans = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
// cout << f[i][j] << " ";
if(f[i][j] == inf) continue;
ans += (ULL)f[i][j] * f[i][j];
}
// cout << "\n";
}
cout << ans;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
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: 3592kb
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: 3828kb
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 ........................................................................................................#................................................................................................................................................................#................