QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#671932#7733. Cool, It’s Yesterday Four Times Morewangxiaorui#WA 45ms8736kbC++141.7kb2024-10-24 15:02:212024-10-24 15:02:22

Judging History

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

  • [2024-10-24 15:02:22]
  • 评测
  • 测评结果:WA
  • 用时:45ms
  • 内存:8736kb
  • [2024-10-24 15:02:21]
  • 提交

answer

#include<bits/stdc++.h>
#define pos(x,y) ((x-1)*n+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);
    if(f[p1][p2]||vis[xb][yb]) return;
    vis[xb][yb]=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&&f2) continue;
        if(f1)
        {
            f[p2][p1]=1;
            continue;
        }
        if(f2)
        {
            f[p1][p2]=1;
            continue;
        }
        dfs(px,py,qx,qy);
    }
}

void sol()
{
    cin>>n>>m;
    memset(f,0,sizeof(f));
    int x=0,xa,ya;
    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;
            memset(vis,0,sizeof(vis));
            for(int k=1;k<=n;k++)
            {
                for(int l=1;l<=m;l++)
                {
                    if(a[k][l]=='O'||vis[k][l]||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: 8736kb

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: 45ms
memory: 8608kb

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
2
3
4
3
0
2
0
2
0
1
4
4
4
2
0
0
3
3
3
1
1
1
0
2
0
2
1
2
1
0
2
2
2
2
0
3
4
2
2
3
2
2
3
2
1
0
3
3
3
2
2
2
0
4
1
1
3
2
3
2
3
2
1
2
1
1
0
0
2
3
1
2
2
3
1
3
2
2
3
3
2
2
1
0
1
1
3
2
6
0
1
2
1
0
0
1
1
1
2
1
2
3
0
3
3
2
3
1
1
3
1
0
2
4
2
2
2
0
1
4
2
2
1
2
1
0
2
0
3
2
3
2
4
0
3
1
3
1
1
...

result:

wrong answer 12th lines differ - expected: '7', found: '2'