Submission #38071367

---

Source Code Expand

#include<bits/stdc++.h>
#define N 90009
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
inline ll rd(){
	ll x=0;char c=getchar();bool f=0;
	while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?-x:x;
}
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
queue<int>q;
int deep[N],head[N],cur[N],n,m,tot=1,tag[N];
char s[309][309];
int id[309][309],tt;
struct edge{
	int n,to,l;
}e[N*20];
inline void add(int u,int v,int l){
	e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;
	e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=0;
}
bool bfs(int s,int t){
	memset(deep,0x3f,sizeof(deep));
	deep[s]=0;
	for(int i=0;i<=t;++i)cur[i]=head[i];
	q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];i;i=e[i].n){
			int v=e[i].to;
			if(e[i].l&&deep[v]==inf){
				deep[v]=deep[u]+1;
				q.push(v);
			} 
		}
	}
	return deep[t]!=inf;
}
int dfs(int s,int t,int l){
	if(s==t||!l)return l;
	int flow=0,f;
	for(int i=cur[s];i;i=e[i].n){
		int v=e[i].to;cur[s]=i;
		if(deep[v]==deep[s]+1&&(f=dfs(v,t,min(e[i].l,l)))){
			flow+=f;l-=f;
			e[i].l-=f;e[i^1].l+=f;
			if(!l)break;
		}
	}
	return flow;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>(s[i]+1);
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j)id[i][j]=++tt;
	}
	int pp=0;
	int S=tt+1,T=tt+2;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j)if(s[i][j]!='1'){
			if((i+j)&1){
				add(S,id[i][j],1);
				if(s[i][j]=='2')tag[id[i][j]]=1;
				for(int k=0;k<4;++k){
					int xx=i+dx[k];
					int yy=j+dy[k];
					if(xx<1||xx>n||yy<1||yy>m)continue;
					if(s[xx][yy]!='1')add(id[i][j],id[xx][yy],1);
				}
			//	if(s[i][j]=='?')add(id[i][j],T,1);
			}
			else{
				if(s[i][j]=='2')tag[id[i][j]]=2;
				add(id[i][j],T,1);
			//	if(s[i][j]=='?')add(S,id[i][j],1);
			}
		}
	} 
	int ans=0;
	while(bfs(S,T))ans+=dfs(S,T,inf);
	int gg=0;
	for(int i=head[S];i;i=e[i].n){
		int v=e[i].to;
	//	cout<<v<<" ? "<<e[i].l<<" "<<tag[v]<<endl;
		if(tag[v]==1&&e[i].l)gg=1;
	}
	for(int i=head[T];i;i=e[i].n){
		int v=e[i].to;
//		cout<<v<<" "<<e[i].l<<" "<<tag[v]<<endl;
		if(tag[v]==2&&e[i].l==0)gg=1;
	}
	if(gg==0)cout<<"Yes";
	else cout<<"No";
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:65:6: warning: unused variable ‘pp’ [-Wunused-variable]
   65 |  int pp=0;
      |      ^~

Judge Result