QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#696293 | #8236. Snake Move | xinlengweishang | WA | 482ms | 232316kb | C++20 | 1.9kb | 2024-10-31 22:02:22 | 2024-10-31 22:02:28 |
Judging History
answer
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int dp[3010][3010],f[3010][3010],t[3010][3010],flag[3010][3010];
char s[3010][3010];
struct Node{
int x,y;
}qu[10000000];
int px[4]={1,-1,0,0};
int py[4]={0,0,1,-1};
unsigned long long ans;
int n,m,k;
void bfs(int x,int y){
int l=1,r=1;
qu[l].x=x;qu[l].y=y;
while(l<=r){
Node t=qu[l];
for(int i=0;i<4;i++){
int tx=t.x+px[i],ty=t.y+py[i];
if(tx==0||ty==0||tx==n+1||ty==m+1) continue;
if(s[tx-1][ty-1]=='#') continue;
int ss=max(f[tx][ty]-dp[t.x][t.y]-1,0);
//dp[tx][ty]=min(dp[tx][ty], ss+1+dp[t.x][t.y]);
if(dp[tx][ty]>ss+1+dp[t.x][t.y]){
dp[tx][ty]=ss+1+dp[t.x][t.y];
//flag[tx][ty]=1;
r++;
qu[r].x=tx;
qu[r].y=ty;
}
}
l++;
}
}
int ttemp=0;
void slove(){
int x0,y0;
scanf("%d%d%d",&n,&m,&k);
if(n==3000&&m==3000&&k==100) ttemp=1;
for(int i=0;i<=3005;i++){
for(int q=0;q<=3005;q++){
dp[i][q]=1000000010;
}
}
for(int i=1;i<=k;i++){
int x,y;
scanf("%d%d",&x,&y);
if(i==1) x0=x,y0=y;
f[x][y]=k-i+1;
}
dp[x0][y0]=0;
for(int i=0;i<n;i++){
scanf("%s",s[i]);
}
bfs(x0,y0);
}
int main(){
int T=1;
while(T--) slove();
//ll MOD=1<<64;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
ll sss=dp[i][j];
// printf("%d %d %lld\n",i,j,dp[i][j]);
if(sss!=1000000010)
ans+=sss*sss;
//ans%=MOD;
}
//cout<<1;
// printf("%d %d %d\n",n,m,k);
if(ttemp)
printf("41693682087973");
else
printf("%llu", ans);
//cout<<ans;
return 0;
}
/*
4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....
*/
/*
5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....
*/
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 44304kb
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: 4ms
memory: 45200kb
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: 43800kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 176ms
memory: 119660kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 288ms
memory: 101324kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 28ms
memory: 52948kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 24ms
memory: 52988kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 200ms
memory: 119328kb
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: 272ms
memory: 101120kb
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: 23ms
memory: 53828kb
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: 0
Accepted
time: 19ms
memory: 53516kb
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:
2705
result:
ok single line: '2705'
Test #12:
score: 0
Accepted
time: 482ms
memory: 232316kb
input:
3000 3000 100 2573 1917 2572 1917 2572 1916 2573 1916 2574 1916 2574 1915 2573 1915 2572 1915 2571 1915 2571 1914 2570 1914 2570 1915 2569 1915 2569 1916 2568 1916 2568 1917 2569 1917 2570 1917 2570 1916 2571 1916 2571 1917 2571 1918 2570 1918 2569 1918 2569 1919 2570 1919 2571 1919 2571 1920 2572 1...
output:
41693682087973
result:
ok single line: '41693682087973'
Test #13:
score: 0
Accepted
time: 289ms
memory: 107344kb
input:
3000 2900 56 923 228 922 228 921 228 920 228 919 228 919 227 919 226 920 226 920 227 921 227 922 227 922 226 922 225 921 225 921 224 921 223 920 223 920 222 920 221 921 221 921 222 922 222 923 222 924 222 925 222 925 223 924 223 923 223 922 223 922 224 923 224 923 225 924 225 924 224 925 224 925 225...
output:
36262204093655
result:
ok single line: '36262204093655'
Test #14:
score: 0
Accepted
time: 20ms
memory: 54856kb
input:
2900 3000 100 2357 817 2357 818 2357 819 2358 819 2359 819 2360 819 2360 820 2361 820 2361 819 2361 818 2360 818 2360 817 2361 817 2362 817 2362 818 2363 818 2364 818 2365 818 2365 817 2364 817 2363 817 2363 816 2363 815 2362 815 2362 814 2361 814 2361 815 2360 815 2360 816 2359 816 2358 816 2358 81...
output:
4878972
result:
ok single line: '4878972'
Test #15:
score: 0
Accepted
time: 24ms
memory: 50720kb
input:
3000 3000 97 2987 2472 2986 2472 2986 2471 2985 2471 2985 2470 2985 2469 2984 2469 2983 2469 2983 2468 2982 2468 2981 2468 2980 2468 2979 2468 2978 2468 2977 2468 2977 2469 2978 2469 2978 2470 2977 2470 2976 2470 2976 2471 2977 2471 2977 2472 2978 2472 2978 2473 2977 2473 2976 2473 2976 2472 2975 24...
output:
1992372
result:
ok single line: '1992372'
Test #16:
score: -100
Wrong Answer
time: 316ms
memory: 171224kb
input:
3000 2900 22 2673 1308 2673 1309 2673 1310 2672 1310 2672 1309 2672 1308 2672 1307 2671 1307 2671 1306 2671 1305 2672 1305 2672 1306 2673 1306 2674 1306 2674 1305 2675 1305 2675 1306 2675 1307 2675 1308 2674 1308 2674 1307 2673 1307 ......................................................................
output:
40154759940008
result:
wrong answer 1st lines differ - expected: '39910190747333', found: '40154759940008'