QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#425543#4773. Piece it togetherGe_QingHuiTL 5ms17908kbC++141.9kb2024-05-30 13:21:152024-05-30 13:21:16

Judging History

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

  • [2024-05-30 13:21:16]
  • 评测
  • 测评结果:TL
  • 用时:5ms
  • 内存:17908kb
  • [2024-05-30 13:21:15]
  • 提交

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...

output:


result: