QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#587023 | #8236. Snake Move | SLF666# | WA | 1208ms | 225404kb | C++17 | 2.3kb | 2024-09-24 17:09:45 | 2024-09-24 17:09:46 |
Judging History
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'