QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719230#7733. Cool, It’s Yesterday Four Times MorePittowWA 1ms5680kbC++171.5kb2024-11-06 23:30:102024-11-06 23:30:11

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 23:30:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5680kb
  • [2024-11-06 23:30:10]
  • 提交

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;
}

詳細信息

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'