QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#719230 | #7733. Cool, It’s Yesterday Four Times More | Pittow | WA | 1ms | 5680kb | C++17 | 1.5kb | 2024-11-06 23:30:10 | 2024-11-06 23:30:11 |
Judging History
answer
#include<cstdio>
int T,n,m,i,j,x,y;
int a[1024][1024],b[1024][1024];//a:1=kangaroo 0=hole b:dead flag
bool v[1024][1024],B;
void dfs(int x,int y){
if(x-i<0||x-i>=n||y-j<0||y-j>=m){
B=0;
return;
}
if(!a[x-i][y-j]){
B=0;
return;
}
if(v[x][y])return;
v[x][y]=1;
if(B&&x>0&&a[x-1][y])dfs(x-1,y);
if(B&&x+1<n&&a[x+1][y])dfs(x+1,y);
if(B&&y>0&&a[x][y-1])dfs(x,y-1);
if(B&&y+1<m&&a[x][y+1])dfs(x,y+1);
}
void clear(int x,int y){
if(b[x][y])return;
b[x][y]=1;
if(x>0&&a[x-1][y])clear(x-1,y);
if(x+1<n&&a[x+1][y])clear(x+1,y);
if(y>0&&a[x][y-1])clear(x,y-1);
if(y+1<m&&a[x][y+1])clear(x,y+1);
}
int main(){
//freopen("a.txt","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(i=0;i<n;++i)
for(j=0;j<m;++j){
char c;
while(c=getchar(),c!='O'&&c!='.');
if(c=='O')a[i][j]=0;
else a[i][j]=1;
b[i][j]=0;
}
for(i=-n+1;i<n;++i)
for(j=-m+1;j<m;++j)if(i||j){
for(x=0;x<n;++x)
for(y=0;y<m;++y)v[x][y]=0;
for(x=i>0?i:0;x<n&&x<n+i;++x)
for(y=j>0?j:0;y<m&&y<m+j;++y)if(a[x][y]&&!v[x][y]){
B=1;
dfs(x,y);
if(B)clear(x,y);
}
}
x=0;
for(i=0;i<n;++i)
for(j=0;j<m;++j)if(a[i][j]&&!b[i][j])++x;
printf("%d\n",x);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5680kb
input:
4 2 5 .OO.. O..O. 1 3 O.O 1 3 .O. 2 3 OOO OOO
output:
3 1 0 0
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5640kb
input:
200 2 4 OOO. OO.. 2 3 OOO .O. 3 3 O.O OOO OO. 4 1 . . O O 1 2 .O 1 1 . 2 5 .OO.. .O.O. 2 1 O O 1 1 O 1 3 .OO 5 1 O O . O . 5 2 O. .. O. .O .. 5 3 ... ... .OO ..O OOO 3 5 ..O.O .O.O. .OO.O 5 2 .O OO O. O. .. 2 1 O O 3 5 .O.OO O...O ..OO. 1 5 ..... 5 1 O . O . . 5 3 OOO OO. .OO OO. O.O 2 1 O . 5 2 O. ...
output:
3 0 0 2 1 1 3 0 0 1 0 0 0 0 4 0 0 0 2 0 1 6 0 0 2 0 0 0 3 3 1 0 1 0 0 0 2 0 0 0 0 0 2 2 2 0 0 6 0 3 0 2 0 2 2 1 0 3 3 0 4 2 2 0 0 6 0 0 0 3 2 5 2 1 2 1 0 0 0 2 0 1 0 0 6 1 0 2 2 3 4 0 2 1 0 1 0 3 0 0 0 0 2 1 0 0 0 0 1 4 0 0 3 0 3 3 2 2 1 0 3 0 0 2 0 2 2 0 0 0 4 0 2 1 2 0 0 0 0 0 4 3 2 0 0 0 0 3 1 1 ...
result:
wrong answer 12th lines differ - expected: '7', found: '0'