Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<algorithm>
- #include<cmath>
- #include<cstring>
- #include<string>
- #include<vector>
- #include<stack>
- #include<queue>
- #include<deque>
- #include<cstdio>
- #include<fstream>
- #include<map>
- #include<set>
- using namespace std;
- const int maxe=(1<<14),maxel=64,maxn=(1<<12),inf=(1<<30);
- struct edge
- {
- int to,cap,next;
- edge(){}
- edge(int _to,int _cap,int _next)
- {
- to=_to;
- cap=_cap;
- next=_next;
- }
- };
- edge e[maxe];int bre;
- int sum_of_a;
- int n,m,allv,a[maxel][maxel],S,T,F,p;
- int head[maxn],ptr[maxn],path[maxn],sz=0;
- int lvl[maxn];
- void read()
- {
- cin>>n>>m;
- string s;
- for(int i=1;i<=n;i++)
- {
- cin>>s;
- for(int j=0;j<m;++j)
- {
- switch(s[j])
- {
- case 'H':a[i][j+1]=1;
- sum_of_a+=a[i][j+1];
- break;
- case 'O':a[i][j+1]=2;
- sum_of_a+=a[i][j+1];
- break;
- case 'N':a[i][j+1]=3;
- sum_of_a+=a[i][j+1];
- break;
- case 'C':a[i][j+1]=4;
- sum_of_a+=a[i][j+1];
- break;
- }
- }
- }
- }
- void add_edge(int from,int to,int cap)
- {
- e[bre]=edge(to,cap,head[from]);
- head[from]=bre;bre++;
- }
- void init_graph()
- {
- memset(head,-1,sizeof(head));
- S=0;T=n*m+1;
- int cur,cur1;
- for(int i=1;i<=n;++i)
- for(int j=1;j<=m;++j)
- {
- if(a[i][j])
- {
- cur=(i-1)*m+j;
- //if((i%2==1&&j%2==1)||(i%2==0&&j%2==0))
- if(i%2==j%2)
- {
- add_edge(S,cur,a[i][j]);
- add_edge(cur,S,0);
- if(1<i)
- {
- if(a[i-1][j])
- {
- cur1=(i-2)*m+j;
- add_edge(cur,cur1,1);
- add_edge(cur1,cur,0);
- }
- }
- if(i<n)
- {
- if(a[i+1][j])
- {
- cur1=(i)*m+j;
- add_edge(cur,cur1,1);
- add_edge(cur1,cur,0);
- }
- }
- if(1<j)
- {
- if(a[i][j-1])
- {
- cur1=(i-1)*m+j-1;
- add_edge(cur,cur1,1);
- add_edge(cur1,cur,0);
- }
- }
- if(j<m)
- {
- if(a[i][j+1])
- {
- cur1=(i-1)*m+j+1;
- add_edge(cur,cur1,1);
- add_edge(cur1,cur,0);
- }
- }
- }
- else
- {
- add_edge(cur,T,a[i][j]);
- add_edge(T,cur,0);
- }
- }
- }
- }
- bool BFS()
- {
- memset(lvl,0,sizeof(lvl));
- lvl[T]=1;
- queue<int>q;
- q.push(T);
- int w;
- while(!q.empty())
- {
- w=q.front();
- q.pop();
- for(int i=head[w];i!=-1;i=e[i].next)
- if(lvl[e[i].to]==0&&e[i^1].cap>0)
- {
- lvl[e[i].to]=lvl[w]+1;
- q.push(e[i].to);
- }
- }
- return lvl[S];
- }
- bool DFS(int ver)
- {
- if(ver==T)return true;
- for(int i=ptr[ver];i!=-1;i=ptr[ver]=e[i].next)
- if(lvl[e[i].to]+1==lvl[ver]&&e[i].cap>0)
- {
- if(DFS(e[i].to))
- {
- if(p>e[i].cap)
- p=e[i].cap;
- path[sz]=i;
- sz++;
- return true;
- }
- }
- return false;
- }
- void inline update()
- {
- int x;
- for(int i=0;i<sz;++i)
- {
- x=path[i];
- e[x].cap-=p;
- e[x^1].cap+=p;
- }
- }
- void Dinitz()
- {
- while(BFS())
- {
- for(int i=0;i<=n*m+1;++i)
- ptr[i]=head[i];
- sz=0;
- p=inf;
- while(DFS(S))
- {
- F+=p;
- update();
- sz=0;
- p=inf;
- }
- }
- if(sum_of_a%2)
- cout<<"Invalid\n";
- else if(F*2==sum_of_a)
- cout<<"Valid\n";
- else cout<<"Invalid\n";
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- read();
- init_graph();
- /*cout<<"Initializated graph\n";
- for(int i=0;i<=n*m+1;i++)
- {
- cout<<"i=="<<i<<endl;
- for(int j=head[i];j!=-1;j=e[j].next)
- cout<<e[j].to<<' '<<e[j].cap<<endl;
- cout<<endl;
- }
- cout<<endl;*/
- Dinitz();
- return 0;
- }
- /*
- 3 4
- HOH.
- NCOH
- OO..
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement