代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define wh ((i&1)?1:-1)
const int inf = 1e9+7;
int g[110][110],s,t,n,to[100100],head[100100],w[100100],nxt[100100];
int level[100100],cur[100100],cnt,ano[100100];
inline void init(){
memset(head,0,sizeof(head));
cnt=0;
}
inline void add(int x,int y,int z){
nxt[++cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
w[cnt]=z;
nxt[++cnt]=head[y];
head[y]=cnt;
to[cnt]=x;
w[cnt]=z;
ano[cnt]=cnt-1;
ano[cnt-1]=cnt;
}
inline void deal(){
int i,j,k;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(g[i][j]==0)add(i,j,2);
else if(g[i][j]==1)add(i,j,inf);
}
inline bool bfs(){
memset(level,-1,sizeof(level));
queue<int>q;
q.push(s);
level[s]=0;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nxt[i])
if(w[i]&&level[to[i]]==-1){
level[to[i]]=level[x]+1;
if(to[i]==t)return 1;
q.push(to[i]);
}
}
return 0;
}
inline int dfs(int x,int flow){
if(x==t)return flow;
int res=0;
cur[x]=head[x];
for(int i=cur[x];i;i=nxt[i]){
cur[x]=i;
int y=to[i];
if(level[y]==level[x]+1&&w[i]){
int f=dfs(y,min(flow-res,w[i]));
res+=f;
w[i]-=f;
w[ano[i]]+=f;
}
}
if(!res)level[x]=-1;
return res;
}
int main(){
int a1,a2,b1,b2,an,bn,i,j,k,Ans1,Ans2;
while(~scanf("%d",&n)){
scanf("%d%d%d%d%d%d",&a1,&a2,&an,&b1,&b2,&bn);
a1++,a2++,b1++,b2++;
for(i=1;i<=n;i++){
char s[70];
scanf("%s",s);
for(j=0;j<n;j++){
if(s[j]=='O')g[i][j+1]=0;
else if(s[j]=='N')g[i][j+1]=1;
else g[i][j+1]=2;
}
}
init();
Ans1=0;
deal();
s=n+1,t=n+2;
add(s,a1,an<<1),add(s,b1,bn<<1);
add(a2,t,an<<1),add(b2,t,bn<<1);
while(bfs())while(int a=dfs(s,inf))Ans1+=a;
init();
Ans2=0;
deal();
s=n+1,t=n+2;
add(s,a1,an<<1),add(s,b2,bn<<1);
add(a2,t,an<<1),add(b1,t,bn<<1);
while(bfs())while(int a=dfs(s,inf))Ans2+=a;
if(Ans1!=(an<<1)+(bn<<1)||Ans2!=(an<<1)+(bn<<1))puts("No");
else puts("Yes");
}
return 0;
}