QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765362#7733. Cool, It’s Yesterday Four Times MoresongziyanWA 1ms4048kbC++172.1kb2024-11-20 14:02:542024-11-20 14:02:55

Judging History

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

  • [2024-11-20 14:02:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4048kb
  • [2024-11-20 14:02:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0;char ch;
    do ch=getchar();while(ch<'0'||ch>'9');
    do x=(x<<3)+(x<<1)+(ch^48),ch=getchar();while(ch>='0'&&ch<='9');
    return x;
}
inline int readchar(){
    char ch;
    do ch=getchar();while(ch!='O'&&ch!='.');
    return ch=='O'?1:0;
}
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
#define pii pair<int,int>
#define fi first
#define se second
int n,m;
int calc(int x,int y){return x*(m+2)+y;}
int calc(pii k){return calc(k.fi,k.se);}
pii invc(int k){return {k/(m+2),k%(m+2)};}
void solve(){
    n=read(),m=read();
    vector<vector<bool>>a(n+5,vector<bool>(m+5,0));
    vector<vector<bool>>f((n+5)*(m+5),vector<bool>((n+5)*(m+5),0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=readchar();
        }
    }
    queue<pii>Q;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        if(a[i][j])continue;
        int p=calc(i,j);
        for(int x=0;x<=n+1;x++)for(int y=0;y<=m+1;y++){
            if(!a[x][y])continue;
            int q=calc(x,y);
            f[p][q]=1;
            Q.push({p,q});
        }
    }
    auto ck=[&](pii k){return 0<=k.fi&&k.fi<=n+1&&0<=k.se&&k.se<=m+1&&!a[k.fi][k.se];};
    auto check=[&](pii k){return ck(invc(k.fi))&&ck(invc(k.se))&&!f[k.fi][k.se];};
    while(!Q.empty()){
        pii s=Q.front();Q.pop();
        pii w=invc(s.fi),l=invc(s.se);
        for(int i=0;i<4;i++){
            pii t={calc(w.fi+dx[i],w.se+dy[i]),calc(l.fi+dx[i],l.se+dy[i])};
            if(check(t)){
                f[t.fi][t.se]=1;
                Q.push(t);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        if(a[i][j])continue;
        int p=calc(i,j);
        int flg=1;
        for(int x=1;x<=n;x++)for(int y=1;y<=n;y++){
            if(a[x][y])continue;
            if(x==i&&y==j)continue;
            int q=calc(x,y);
            flg&=f[p][q];
        }
        ans+=flg;
    }
    printf("%d\n",ans);
}
int main(){
    int T=read();
    while(T--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4048kb

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

3
1
1
0

result:

wrong answer 3rd lines differ - expected: '0', found: '1'