QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#360894 | #8236. Snake Move | whsyhyyh# | WA | 310ms | 141972kb | C++14 | 1.9kb | 2024-03-22 14:13:37 | 2024-03-22 14:13:37 |
Judging History
answer
#include<bits/stdc++.h>
#define N 3010
#define LL long long
#define rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
int rd() {
int res=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
return res*f;
}
int n,m,K;
int mp[N][N],snk[N][2],dis[N][N];
char ch[N];
int qu[N*N*2][2],hd=1,tl;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void bfs() {
memset(dis,63,sizeof(dis));
dis[snk[1][0]][snk[1][1]]=0,qu[++tl][0]=snk[1][0],qu[tl][1]=snk[1][1];
int x,y,now;
while(hd<=tl) {
x=qu[hd][0],y=qu[hd++][1];
now=dis[x][y];
int wasx=x,wasy=y;
if(now<K&&(hd==1||now!=dis[qu[hd-2][0]][qu[hd-2][1]])) {
x=snk[K-now][0],y=snk[K-now][1];
for(int i=0,xx,yy;i<=3;i++) {
xx=x+dx[i],yy=y+dy[i];
if(dis[xx][yy]<0x3f3f3f3f) {
if(dis[x][y]>now+1) {
dis[x][y]=now+1;
qu[++tl][0]=x,qu[tl][1]=y;
}
}
}
}
x=wasx,y=wasy;
for(int i=0,xx,yy;i<=3;i++) {
xx=x+dx[i],yy=y+dy[i];
if(mp[xx][yy]<=dis[x][y]+1) {
if(dis[xx][yy]>dis[x][y]+1) {
dis[xx][yy]=dis[x][y]+1;
qu[++tl][0]=xx,qu[tl][1]=yy;
}
}
}
}
}
int main() {
n=rd(),m=rd(),K=rd();
memset(mp,63,sizeof(mp));
rep(i,1,K) snk[i][0]=rd(),snk[i][1]=rd();
rep(i,1,n) {
scanf("%s",ch+1);
rep(j,1,m) if(ch[j]=='.') mp[i][j]=0;
}
rep(i,1,K) mp[snk[i][0]][snk[i][1]]=K-i+1;
bfs();
LL ans=0;
rep(i,1,n) rep(j,1,m) if(dis[i][j]<0x3f3f3f3f) ans+=1ll*dis[i][j]*dis[i][j];
printf("%lld",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 74580kb
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: 74644kb
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: 7ms
memory: 74656kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 150ms
memory: 141972kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 302ms
memory: 120740kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 66ms
memory: 74532kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 38ms
memory: 74576kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 150ms
memory: 141928kb
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: 310ms
memory: 122416kb
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: 64ms
memory: 74696kb
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: 40ms
memory: 74680kb
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'