QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#587108#8236. Snake MoveSLF666#TL 0ms3624kbC++172.0kb2024-09-24 17:37:282024-09-24 17:37:28

Judging History

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

  • [2024-09-24 17:37:28]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3624kb
  • [2024-09-24 17:37:28]
  • 提交

answer

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

#define ll long long
#define ull unsigned long long
//#define int ull
#define endl "\n"

int nt[4][2] = {
	{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};

void solve(){
	ull n, m, k;
	cin >> n >> m >> k;
	map<pair<int, int>, ull> mp;
	int i;
	int nowx1 = -1, nowy1 = -1;
	int nowx2 = -1, nowy2 = -1;
	for(i = 0 ; i < k ; i ++) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		if(i == 0) {
			nowx1 = x;
			nowy1 = y;
		}
		if(i == 1) {
			nowx2 = x;
			nowy2 = y;
		}
		if(i != 0) mp[{x, y}] = k - i;
	}
	vector<vector<ull>> f1(n + 3, vector<ull>(m + 3, 1e18)), f2(n + 3, vector<ull>(m + 3, 1e18));
	vector<vector<ull>> book(n + 3, vector<ull>(m + 3, 0));
	vector<string> a(n + 3);
	int j;
	for(i = 0 ; i < n ; i ++) {
		cin >> a[i];
	}
	
	priority_queue<pair<ull, pair<int, int>>, vector<pair<ull, pair<int, int>>>, greater<pair<ull, pair<int, int>>> > q;
	q.push({0, {nowx1, nowy1}});
	while(!q.empty()) {
		auto it = q.top();
		q.pop();
		int x = it.second.first;
		int y = it.second.second;
		ull step = it.first;
		if(x < 0 || y < 0 || x >= n || y >= m) continue;
		if(a[x][y] == '#') continue;
		f1[x][y] = min(f1[x][y], step);
		if(mp.find({x, y}) != mp.end()) {
			f1[x][y] = max(mp[{x, y}], f1[x][y]);
		}
		if(book[x][y]) continue;
		book[x][y] = 1;
		for(i = 0 ; i < 4 ; i ++) {
			int nx = x + nt[i][0], ny = y + nt[i][1];
			int ss = f1[x][y] + 1;
			q.push({ss, {nx, ny}});
		}
	}
	
	for(i = 0 ; i <= n ; i ++) {
		for(j = 0 ; j <= m ; j ++) book[i][j] = 0;
	}
	
	ull ans = 0;
	
	for(i = 0 ; i < n ; i ++) {
		for(j = 0 ; j < m ; j ++) {
			f1[i][j] = min(f1[i][j], f2[i][j]);
			if(f1[i][j] == 1e18) continue;
			ans += f1[i][j] * f1[i][j];
//			cout << f1[i][j] << ' ';
		}
//		cout << endl;
	}
	
	cout << ans << endl;
	
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t = 1;
//	cin>>t;
	for(int i=1;i<=t;i++)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

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: 0ms
memory: 3600kb

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

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:

35141960580077

result: