QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#425543 | #4773. Piece it together | Ge_QingHui | TL | 5ms | 17908kb | C++14 | 1.9kb | 2024-05-30 13:21:15 | 2024-05-30 13:21:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+9;
int n,m,cnt,mat[N],id[2][509][509];
bool vst[N];
char mp[509][509];
vector<int> Eg[N];
bool dfs(int x){
vst[x]=1;
for(int u:Eg[x]){
int v=mat[u];
if(v<0 || !vst[v] && dfs(v)){
mat[x]=u; mat[u]=x;
return true;
}
}
return false;
}
int calc(){
int res=0;
memset(mat,-1,sizeof(mat));
for(int i=1;i<=cnt;i++){
if(mat[i]<0){
memset(vst,0,sizeof(vst));
if(dfs(i)) res++;
}
}
return res;
}
const int dx[5]={0,0,1,-1};
const int dy[5]={1,-1,0,0};
inline void add(int x,int y){
Eg[x].push_back(y);
Eg[y].push_back(x);
}
void solve(){
cnt=0; cin>>n>>m;
for(int i=1;i<=500000;i++) Eg[i].clear();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) cin>>mp[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(mp[i][j]=='.') continue;
if(mp[i][j]=='W') id[0][i][j]=++cnt;
if(mp[i][j]=='B') id[0][i][j]=++cnt,id[1][i][j]=++cnt;
}
int sB=0,sW=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(mp[i][j]=='B'){
for(int k=0;k<4;k++){
int ni=i+dx[k],nj=j+dy[k];
if(1<=ni && ni<=n && 1<=nj && nj<=m && mp[ni][nj]=='W'){
add(id[(k<2)][i][j],id[0][ni][nj]);
}
}
sB++;
}
else if(mp[i][j]=='W') sW++;
}
if(sB*2!=sW || calc()!=sW){
cout<<"NO\n";
}
else cout<<"YES\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
int T; cin>>T;
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 17908kb
input:
2 3 4 BWW. WWBW ..WB 3 3 W.. BW. WBW
output:
YES NO
result:
ok 2 token(s): yes count is 1, no count is 1
Test #2:
score: -100
Time Limit Exceeded
input:
70 3 4 BWW. WWBW ..WB 3 3 W.. BW. WBW 1 1 B 3 3 ... .W. ... 2 2 W. BW 2 3 .W. WBW 1 3 WBW 2 5 .W.W. WB.BW 2 2 WW .B 2 2 WB .. 3 3 WWB BWW WWB 3 5 .W.WB WBW.W ...WB 4 5 ..W.. .WBW. WBWBW .WBW. 3 9 BWW...W.. WWBW..BW. ..WB..WBW 4 12 BWWBWWBWWBWW WWBWWBWWBWWB BWWBWWBWWBWW WWBWWBWWBWWB 7 7 BWWBBWW WBWWW...