QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #823787 | #8236. Snake Move | mx26# | WA | 259ms | 152352kb | C++14 | 1.4kb | 2024-12-21 09:41:09 | 2024-12-21 09:41:38 |
Judging History
answer
#include<bits/stdc++.h>
#define Ri register int
#define LL unsigned long long
using namespace std;
const int inf=1e9+7;
const int N=3015;
int X[N*N],Y[N*N],dis[N][N],vis[N][N],q[N*N][2];
const int fx[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
char s[N][N];
int n,m,K;
void Sol(){
scanf("%d %d %d",&n,&m,&K);
for(Ri i=1; i<=n; ++i){
for(Ri j=1; j<=m; ++j){
dis[i][j]=inf;
vis[i][j]=0;
}
}
for(Ri i=1; i<=K; ++i){
scanf("%d %d",&X[i],&Y[i]);
vis[X[i]][Y[i]]=K-i+1;
}
dis[X[1]][Y[1]]=0,vis[X[1]][Y[1]]=0;
for(Ri i=1; i<=n; ++i){
scanf("%s",s[i]+1);
}
int l=1,r=1;
q[1][0]=X[1],q[1][1]=Y[1];
LL ans=0;
while(l<=r){
int x=q[l][0],y=q[l][1];
l++;
int oo=dis[x][y];
ans+=oo*oo;
if(oo<K-1){
int xx=X[K-oo],yy=Y[K-oo];
if(vis[xx][yy]>0){
vis[xx][yy]=0;
int QAQ=0;
for(Ri i=0; i<4; ++i){
int xxx=xx+fx[i][0],yyy=yy+fx[i][1];
if(xxx<1 || xxx>n || yyy<1 || yyy>m) continue;
if(dis[xxx][yyy]<=oo) QAQ=1;
}
if(QAQ==1) dis[xx][yy]=oo+1,++r,q[r][0]=xx,q[r][1]=yy;
}
}
for(Ri i=0; i<4; ++i){
int xx=x+fx[i][0],yy=y+fx[i][1];
if(s[xx][yy]=='.' && dis[xx][yy]>dis[x][y]+1 && vis[xx][yy]==0){
dis[xx][yy]=dis[x][y]+1;
q[++r][0]=xx,q[r][1]=yy;
}
}
}
// for(Ri i=1; i<=n; ++i){
// for(Ri j=1; j<=m; ++j){
// printf("%d",dis[i][j]);
// }
// printf("\n");
// }
// printf("\n");
printf("%llu\n",ans);
}
int main(){
Sol();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 14132kb
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: 14096kb
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: 2ms
memory: 14196kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 197ms
memory: 152352kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 259ms
memory: 129360kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 19ms
memory: 84912kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 20ms
memory: 85432kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 204ms
memory: 149740kb
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: 254ms
memory: 133156kb
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: 0
Accepted
time: 12ms
memory: 84512kb
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:
40571
result:
ok single line: '40571'
Test #11:
score: -100
Wrong Answer
time: 15ms
memory: 82340kb
input:
2900 3000 10 2447 135 2447 136 2447 137 2447 138 2447 139 2447 140 2448 140 2448 139 2449 139 2449 138 .#.##.##..#.###########.#####.###....#####.########..##..#.####.##.##.####.####..#.#####.##.#.#.###.##.#.##.####..##.#.####..###..###...##...##.#####.#####.#...#####.####..##.##.#.#..#..####.##..##...
output:
170
result:
wrong answer 1st lines differ - expected: '2705', found: '170'