QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#627859 | #8236. Snake Move | zzfs# | RE | 1ms | 5700kb | C++14 | 1.7kb | 2024-10-10 17:24:23 | 2024-10-10 17:24:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5;
int mp[N][N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int vis[N][N];
int res[N][N];
struct node
{
ll x, y, step;
bool operator<(const node &a) const
{
return step > a.step;
}
};
void solve()
{
int n, m, k;
cin >> n >> m >> k;
priority_queue<node> q;
for (int i = 1; i <= k; i++)
{
int a, b;
cin >> a >> b;
mp[a][b] = k - i + 1;
if (i == 1)
q.push({a, b, 0});
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
char ch;
cin >> ch;
if (ch == '#')
mp[i][j] = -1;
}
}
unsigned long long ans = 0;
while (!q.empty())
{
auto [x, y, step] = q.top();
q.pop();
if (vis[x][y])
continue;
vis[x][y] = 1;
ans += step * step;
res[x][y] = step * step;
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 1 || nx > n || ny < 1 || ny > m || mp[nx][ny] == -1 || vis[nx][ny])
continue;
q.push({nx, ny, max(step + 1, 1LL * mp[nx][ny])});
}
}
// for (int i = 1; i <= n; i++)
// {
// for (int j = 1; j <= m; j++)
// cout << res[i][j] << ' ';
// cout << endl;
// }
cout << ans << endl;
}
int main()
{
cin.tie(0)->ios::sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5688kb
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: 5664kb
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: 5700kb
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 ........................................................................................................#................................................................................................................................................................#................