QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#620195#8236. Snake MoveLa5te2RE 0ms0kbC++201.7kb2024-10-07 16:58:062024-10-07 16:58:14

Judging History

你现在查看的是最新测评结果

  • [2024-10-07 16:58:14]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-07 16:58:06]
  • 提交

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
.....
.....
.....
.....

output:


result: