QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#641749 | #8236. Snake Move | snow_miku | WA | 1094ms | 153180kb | C++23 | 2.6kb | 2024-10-14 23:00:26 | 2024-10-14 23:00:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 3001;
const int M = 3001;
ull dis[N][M];
int ff[4];
int tt[4];
int py[N][M];
int vis[N][M];
struct node{
int x;
int y;
// ull w;
ull step;
int len;
bool operator<(const node& b) const {
return step > b.step;
}
};
char s[N][N];
void solve(){
int n, m, k;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
py[i][j] = k + 1;
}
}
// vector<vector<int>> py(n + 1, vector<int> (m + 1, k + 1));
int xx, yy;
cin >> xx >> yy;
py[xx][yy] = 1;
for(int i = 2; i <= k; i++){
int a, b;
cin >> a >> b;
py[a][b] = i;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
cin >> s[i][j];
}
// vector<vector<ull>> dis(n + 1, vector<ull> (m + 1));
auto bfs = [&](){
priority_queue<node> q;
ff[0] = -1;
ff[1] = 1;
tt[2] = 1;
tt[3] = -1;
// vector<vector<int>> vis(n + 1, vector<int> (m + 1));
q.push({xx, yy, 0, k});
while(!q.empty()){
auto [x, y, step, len] = q.top();
q.pop();
if(vis[x][y])continue;
vis[x][y] = 1;
dis[x][y] = step;
for(int p = 0; p < 4; p++){
int u = x + ff[p];
int v = y + tt[p];
if(u <= n && u >= 1 && v <= m && v >= 1){
if(s[u][v] == '.' && vis[u][v] == 0){
if(py[u][v] + step < len){//py + step 代表现在蛇的位置
int cnt = len - py[u][v] + step;
q.push({u, v, dis[x][y] + cnt + 1, len - cnt});
}
else q.push({u, v, dis[x][y] + 1, len});
}
}
}
}
};
bfs();
ull ans = 0;
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= m; j++){
// cout << py[i][j] << " ";
// }
// cout << '\n';
// }
// cout << "---------------" << endl;
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= m; j++){
// cout << dis[i][j] << " ";
// }
// cout << '\n';
// }
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
ans += dis[i][j] * dis[i][j];
}
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7652kb
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: 1ms
memory: 7888kb
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: 7904kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 1094ms
memory: 153168kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 726ms
memory: 150808kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 69ms
memory: 52348kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 70ms
memory: 51344kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 1091ms
memory: 152720kb
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: 0
Accepted
time: 735ms
memory: 153180kb
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:
22509095749285
result:
ok single line: '22509095749285'
Test #10:
score: -100
Wrong Answer
time: 64ms
memory: 53108kb
input:
3000 2900 10 326 1781 325 1781 325 1782 325 1783 325 1784 324 1784 324 1783 323 1783 323 1782 324 1782 ##.#....#.###.######..#.#.....##.#.##..####.####.##..#..#.###.#####....##.#.##.#..###..##.###.##.#####.###..##.#..##..##.#..##.#.#.##...##..#.##.##........#..#..###.##.###.####.#..########.##.....#...
output:
41915
result:
wrong answer 1st lines differ - expected: '40571', found: '41915'