QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#625728#8236. Snake MovezxkRE 2ms11968kbC++172.1kb2024-10-09 20:43:502024-10-09 20:43:52

Judging History

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

  • [2024-10-09 20:43:52]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:11968kb
  • [2024-10-09 20:43:50]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef unsigned long long ULL;

const int N = 3010, inf = 1e18;

int n, m, k;
char g[N][N];
int d[N][N], dist[N][N]; // 离尾巴的距离, 最短路
bool vis[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void bfs(int x, int y)
{
	queue<array<int, 3>> q1;
	priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int,3>> > q2;
	dist[x][y] = 0;
	q1.push({0, x, y});
	vis[x][y] = true;
	while (q1.size() || q2.size())
	{
		array<int, 3> tmp;
		if (q2.size() && q2.top()[0] <= q1.front()[0]) {tmp = q2.top(); q2.pop();}
		else {tmp = q1.front(); q1.pop();}
		auto [cnt, x, y] = tmp;
		for (int i = 0; i < 4; i ++ )
		{
			int nx = x + dx[i], ny = y + dy[i];
			if (nx <= 0 || nx > n || ny <= 0 || ny > m || vis[nx][ny] || g[nx][ny] == '#') continue;
			
			if (d[nx][ny] != -1 && cnt+1 < d[nx][ny])
			{
				q2.push({d[nx][ny], nx, ny});
				dist[nx][ny] = d[nx][ny];
				vis[nx][ny] = true;
			}
			else
			{
				q1.push({cnt+1, nx, ny});
				dist[nx][ny] = cnt + 1;
				vis[nx][ny] = true;
			}
			
			// q2.push({max(cnt+1, d[nx][ny]), nx, ny});
			// dist[nx][ny] = max(cnt+1, d[nx][ny]);
			// vis[nx][ny] = true;
		}
	}
}

signed main()
{
	cin >> n >> m >> k;
	PII start;
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j ++ )
		{
			dist[i][j] = inf;
			d[i][j] = -1;
		}
	for (int i = 0; i < k; i ++ )
	{
		int x, y;
		cin >> x >> y;
		d[x][y] = k - i;
		if (i == 0) start = {x, y};
	}
	
	for (int i = 1; i <= n; i ++ ) 
		for (int j = 1; j <= m; j ++ )
			cin >> g[i][j];
	
	bfs(start.first, start.second);
	
	// for (int i = 1; i <= n; i ++ )
	// {
		// for (int j = 1; j <= m; j ++ )
		// {
			// cout << dist[i][j] << ' ';
		// }
		// cout << '\n';
	// }
	
	unsigned long long ans = 0;
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 1; j <= m; j ++ )
		{
			if (dist[i][j] != inf) ans += 1ull * dist[i][j] * dist[i][j];
		}
	}
	
	cout << ans << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11968kb

input:

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

output:

293

result:

ok single line: '293'

Test #2:

score: -100
Runtime Error

input:

2 2 4
1 1
1 2
2 2
2 1
..
..

output:


result: