QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#725361#8236. Snake MoveChiTangTL 7ms92464kbC++171.6kb2024-11-08 17:18:342024-11-08 17:18:34

Judging History

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

  • [2024-11-08 17:18:34]
  • 评测
  • 测评结果:TL
  • 用时:7ms
  • 内存:92464kb
  • [2024-11-08 17:18:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e5 + 10;

char mp[3300][3300];
int sn[3300][3300];
int pa[3300][3300];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void solve()
{
	int n, m, k;
	cin >> n >> m >> k;
	int num = k;

	int stx, sty;
	for (int i = 1; i <= k; i++)
	{
		int x, y;
		cin >> x >> y;
		if (i == 1)
		{
			stx = x;
			sty = y;
		}
		sn[x][y] = num--;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> mp[i][j];
		}
	}
	memset(pa, 0x3f, sizeof(pa));
	// cout<<pa[stx][sty]<<endl;
	pa[stx][sty] = 0;
	queue<pair<int, int>> q;
	q.push({stx, sty});
	while (q.size())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || ny < 1 || nx > n || ny > m || mp[nx][ny] == '#')
				continue;
			if (pa[x][y] + 1 > pa[nx][ny])
				continue;

			if (sn[nx][ny] > pa[x][y] + 1)
			{

				pa[nx][ny] = min(pa[nx][ny], sn[nx][ny] );
				q.push({nx, ny});
			}
			else
			{

				pa[nx][ny] = min(pa[nx][ny], pa[x][y] + 1);
				q.push({nx, ny});
			}
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			
			if(pa[i][j]==4557430888798830399)continue;
			//cout<<pa[i][j]<<" ";
			ans += pa[i][j]*pa[i][j];
		}
		//cout<<endl;
	}
	cout<<ans<<endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int t = 1;
	//	cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 92464kb

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: 3ms
memory: 92156kb

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: 92232kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: -100
Time Limit Exceeded

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:


result: