QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#765362 | #7733. Cool, It’s Yesterday Four Times More | songziyan | WA | 1ms | 4048kb | C++17 | 2.1kb | 2024-11-20 14:02:54 | 2024-11-20 14:02:55 |
Judging History
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'