QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672493#7733. Cool, It’s Yesterday Four Times Morewangxiaorui#WA 33ms8812kbC++141.9kb2024-10-24 17:01:582024-10-24 17:01:58

Judging History

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

  • [2024-10-24 17:01:58]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:8812kb
  • [2024-10-24 17:01:58]
  • 提交

answer

#include<bits/stdc++.h>
#define pos(x,y) ((x-1)*m+y)
#define fail(x,y) (x<1||y<1||x>n||y>m||a[x][y]=='O')
using namespace std;

const int X[]={1,0,-1,0};
const int Y[]={0,1,0,-1};
char a[1005][1005],vis[1005][1005];
int n,m,f[1005][1005],ans;

void dfs(int xa,int ya,int xb,int yb)
{
    int p1=pos(xa,ya),p2=pos(xb,yb);
    // cerr<<xa<<' '<<ya<<' '<<xb<<' '<<yb<<':'<<p1<<' '<<p2<<' '<<f[p1][p2]<<endl;
    if(f[p1][p2]) return;
    vis[p1][p2]=1;
    for(int i=0;i<4;i++)
    {
        int px=xa+X[i],py=ya+Y[i],qx=xb+X[i],qy=yb+Y[i];
        int f1=fail(px,py),f2=fail(qx,qy);
        if(f1) continue;
        if(f2)
        {
            f[p1][p2]=1;
            continue;
        }
        // cerr<<px<<' '<<py<<' '<<qx<<' '<<qy<<endl;
        if(!vis[pos(px,py)][pos(qx,qy)]) dfs(px,py,qx,qy);
        f[p1][p2]|=f[pos(px,py)][pos(qx,qy)];
    }
}

void sol()
{
    cin>>n>>m;
    memset(f,0,sizeof(f));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int res=1;
            if(a[i][j]=='O') continue;
            for(int k=1;k<=n;k++)
            {
                for(int l=1;l<=m;l++)
                {
                    vis[k][l]=0;
                }
            }
            for(int k=1;k<=n;k++)
            {
                for(int l=1;l<=m;l++)
                {
                    if(a[k][l]=='O'||i==k&&j==l) continue;
                    dfs(i,j,k,l);
                    res&=f[pos(i,j)][pos(k,l)];
                    // cerr<<i<<','<<j<<' '<<k<<','<<l<<' '<<f[pos(i,j)][pos(k,l)]<<endl;
                }
            }
            ans+=res;
        }
    }
    cout<<ans<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--) sol();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 8780kb

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: 33ms
memory: 8812kb

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
7
9
4
4
0
5
5
2
0
1
6
4
5
2
0
0
5
3
3
1
4
1
0
7
5
2
3
7
3
0
6
2
2
2
0
4
6
6
3
3
2
3
5
2
1
0
3
3
4
4
2
2
0
7
6
4
7
5
3
2
5
2
1
2
1
4
0
0
2
5
1
4
6
6
1
6
2
2
3
4
5
2
1
0
1
9
3
4
11
0
3
2
1
0
0
4
3
1
4
3
8
3
0
3
6
2
5
1
3
3
4
0
2
11
2
2
4
0
4
4
6
2
1
2
3
0
5
0
16
4
3
2
6
0
8
3
3
1...

result:

wrong answer 17th lines differ - expected: '6', found: '5'