QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#587023#8236. Snake MoveSLF666#WA 1208ms225404kbC++172.3kb2024-09-24 17:09:452024-09-24 17:09:46

Judging History

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

  • [2024-09-24 17:09:46]
  • 评测
  • 测评结果:WA
  • 用时:1208ms
  • 内存:225404kb
  • [2024-09-24 17:09:45]
  • 提交

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];
	}
	
	queue<array<int, 3>> q;
	q.push({nowx1, nowy1, 0});
	while(!q.empty()) {
		auto it = q.front();
		q.pop();
		int x = it[0], y = it[1];
		ull step = it[2];
		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({nx, ny, ss});
		}
	}
	
	for(i = 0 ; i <= n ; i ++) {
		for(j = 0 ; j <= m ; j ++) book[i][j] = 0;
	}
	
	int ss = k - 1;
	q.push({nowx2, nowy2, ss});
	
	while(!q.empty()) {
		auto it = q.front();
		q.pop();
		int x = it[0], y = it[1];
		ull step = it[2];
		if(x < 0 || y < 0 || x >= n || y >= m) continue;
		if(a[x][y] == '#') continue;
		f2[x][y] = min(f2[x][y], step);
		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 = f2[x][y] + 1;
			q.push({nx, ny, ss});
		}
	}
	
	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;
}

詳細信息

Test #1:

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

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 571ms
memory: 217840kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 608ms
memory: 218076kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 31ms
memory: 224592kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 39ms
memory: 217188kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 1127ms
memory: 218036kb

input:

2900 3000 10
2883 1758
2883 1759
2883 1760
2883 1761
2883 1762
2884 1762
2884 1763
2883 1763
2882 1763
2882 1764
........................................................#............................#........................................................................................................

output:

49803365625286

result:

ok single line: '49803365625286'

Test #9:

score: -100
Wrong Answer
time: 1208ms
memory: 225404kb

input:

3000 3000 10
2015 1932
2015 1931
2015 1930
2015 1929
2016 1929
2017 1929
2018 1929
2018 1928
2018 1927
2017 1927
#...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......

output:

22509095749317

result:

wrong answer 1st lines differ - expected: '22509095749285', found: '22509095749317'