QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#620195 | #8236. Snake Move | La5te2 | RE | 0ms | 0kb | C++20 | 1.7kb | 2024-10-07 16:58:06 | 2024-10-07 16:58:14 |
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
void solve() {
int n, m, k;
cin >> n >> m >> k;
struct node {
ll dis;
PII u;
bool operator < (const node &a)const {return dis > a.dis;}
};
std::vector<vector<char>> g(n + 1, vector<char>(m + 1));
std::vector<vector<ll>> dis(n + 1, vector<ll>(m + 1, 1e18));
std::vector<vector<int>> f(n + 1, vector<int>(m + 1));
std::vector<vector<bool>> vis(n + 1, vector<bool>(m + 1, 0));
std::priority_queue<node> Q;
for(int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
f[x][y] = k - i;
if(i == 1) {
dis[x][y] = 0;
Q.push({0, {x, y}});
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
while(!Q.empty()) {
auto u = Q.top(); Q.pop();
int x = u.u.first, y = u.u.second;
if(vis[x][y]) continue;
vis[x][y] = 1;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
for(int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(nx <= 0 || ny <= 0 || nx > n || ny > m || vis[nx][ny] || g[nx][ny] == '#') continue;
if(dis[nx][ny] > max(dis[x][y] + 1, (ll)f[nx][ny]+1)) {
dis[nx][ny] = max(dis[x][y] + 1, (ll)f[nx][ny]+1);
Q.push({dis[nx][ny], {nx, ny}});
}
}
}
unsigned long long mod = 1;
for(int i = 1; i <= 64; i++) mod *= 2;
unsigned long long ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(dis[i][j] == 1e18) {
dis[i][j] = 0;
}
ans = (ans + dis[i][j] * dis[i][j]) % mod;
}
}
cout << ans ;
return ;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(20);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....