将一个格子看作一个节点，相邻（有公共边）的同色格子之间连边，那么由前两个条件即要求图恰被分为两个非空连通块（由于$n,mge 3$，显然不能不使用某种颜色）
下面，来分析图中的简单环，其对应于网格图上即会将网格图分为了两部分，简单分类讨论不难发现只有这个环恰有最外圈所有节点构成时仍能满足第3个条件
换言之，第3个条件即等价于图上至多存在一个所有最外圈节点所构成的环（由于$n,mge 3$，显然允许存在）
不妨先强制其不存在环，注意到$nmle 100$，不妨假设$nge m$（否则交换），从上到下依次dp，并状压前$m$个点的颜色以及连通性，根据没有环即可转移
若仅保留可能得到的状态，最终状态数不超过$2 imes 10^{4}$，即可以通过
关于最外圈所有节点所构成的环，特判最后两个节点的状态即可
（实现上可能有一些细节，可以参考代码）
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 105 4 #define mod 998244353 5 #define ll long long 6 #define fi first 7 #define se second 8 vector<pair<ll,int> >vv,v[2]; 9 int t,n,m,ans,a[N][N],c[N],bl[N]; 10 ll get_hash(){ 11 ll s=0; 12 for(int i=0;i<m;i++)s=((s<<1)|c[i]); 13 for(int i=0;i<m;i++)s=((s<<4)|bl[i]); 14 return s; 15 } 16 void get_val(ll s){ 17 for(int i=m-1;i>=0;i--,s>>=4)bl[i]=(s&15); 18 for(int i=m-1;i>=0;i--,s>>=1)c[i]=(s&1); 19 } 20 bool check(){ 21 int x=-1,y=-1; 22 for(int i=0;i<m;i++){ 23 if (!c[i]){ 24 if (x<0)x=bl[i]; 25 if (x!=bl[i])return 0; 26 } 27 else{ 28 if (y<0)y=bl[i]; 29 if (y!=bl[i])return 0; 30 } 31 } 32 return 1; 33 } 34 void merge(int x,int y){ 35 if (x>y)swap(x,y); 36 for(int i=0;i<m;i++) 37 if (bl[i]==y)bl[i]=x; 38 } 39 void dfs(int k){ 40 if (k==m){ 41 v[0].push_back(make_pair(get_hash(),1)); 42 return; 43 } 44 if (a[0][k]!=1){ 45 c[k]=0,bl[k]=k; 46 if ((k)&&(!c[k-1]))bl[k]=bl[k-1]; 47 dfs(k+1); 48 } 49 if (a[0][k]!=0){ 50 c[k]=1,bl[k]=k; 51 if ((k)&&(c[k-1]))bl[k]=bl[k-1]; 52 dfs(k+1); 53 } 54 } 55 int calc(ll s,int pos,int p){ 56 get_val(s); 57 if (c[pos]==p){ 58 if (!pos)return 1; 59 if (bl[pos-1]==bl[pos])return 0; 60 if (c[pos-1]==c[pos])merge(bl[pos-1],bl[pos]); 61 return 1; 62 } 63 bool flag=0; 64 for(int i=0;i<m;i++) 65 if ((i!=pos)&&(bl[i]==bl[pos]))flag=1; 66 if (!flag)return 0; 67 c[pos]=p; 68 if (bl[pos]!=pos)bl[pos]=pos; 69 else{ 70 for(int i=0;i<m;i++) 71 if ((i!=pos)&&(bl[i]==pos)){ 72 for(int j=0;j<m;j++) 73 if ((j!=pos)&&(bl[j]==pos))bl[j]=i; 74 break; 75 } 76 } 77 if ((pos)&&(c[pos-1]==c[pos]))bl[pos]=bl[pos-1]; 78 return 1; 79 } 80 int main(){ 81 scanf("%d",&t); 82 while (t--){ 83 scanf("%d%d",&n,&m); 84 if (n>=m){ 85 for(int i=0;i<n;i++) 86 for(int j=0;j<m;j++)scanf("%d",&a[i][j]); 87 } 88 else{ 89 for(int i=0;i<n;i++) 90 for(int j=0;j<m;j++)scanf("%d",&a[j][i]); 91 swap(n,m); 92 } 93 int p=ans=0; 94 v[0].clear(); 95 dfs(0); 96 for(int i=1;i<n;i++) 97 for(int j=0;j<m;j++){ 98 if ((i==n-1)&&(j>=m-2))continue; 99 vv.clear(); 100 for(int k=0;k<v[p].size();k++){ 101 ll s=v[p][k].fi; 102 if ((a[i][j]!=1)&&(calc(s,j,0)))vv.push_back(make_pair(get_hash(),v[p][k].se)); 103 if ((a[i][j]!=0)&&(calc(s,j,1)))vv.push_back(make_pair(get_hash(),v[p][k].se)); 104 } 105 sort(vv.begin(),vv.end()); 106 p^=1; 107 v[p].clear(); 108 for(int k=0;k<vv.size();k++){ 109 if ((!k)||(vv[k].fi!=vv[k-1].fi))v[p].push_back(make_pair(vv[k].fi,0)); 110 v[p].back().se=(v[p].back().se+vv[k].se)%mod; 111 } 112 } 113 int a1=a[n-1][m-2],a2=a[n-1][m-1]; 114 for(int i=0;i<v[p].size();i++){ 115 ll s=v[p][i].fi; 116 get_val(s); 117 if (c[m-2]==c[m-1]){ 118 if ((c[m-3]==c[m-2])||(!check()))continue; 119 if (a1!=c[m-2]){ 120 ans=(ans+v[p][i].se)%mod; 121 if (a2<0)ans=(ans+v[p][i].se)%mod; 122 } 123 continue; 124 } 125 if (c[m-3]==c[m-2]){ 126 if (bl[m-3]==bl[m-2]){ 127 if ((a1!=c[m-2])&&(a2!=c[m-2])){ 128 merge(bl[m-1],bl[m-3]); 129 if (check())ans=(ans+v[p][i].se)%mod; 130 } 131 } 132 else{ 133 if (a1!=c[m-1]){ 134 merge(bl[m-2],bl[m-3]); 135 if (check()){ 136 ans=(ans+v[p][i].se)%mod; 137 if (a2<0)ans=(ans+v[p][i].se)%mod; 138 } 139 } 140 } 141 } 142 else{ 143 if (bl[m-3]!=bl[m-1]){ 144 if ((a1!=c[m-2])&&(a2!=c[m-2])){ 145 merge(bl[m-1],bl[m-3]); 146 if ((check()))ans=(ans+v[p][i].se)%mod; 147 } 148 } 149 else{ 150 if (!check())continue; 151 int ss=v[p][i].se; 152 if (a1<0)ss=(ss<<1)%mod; 153 if (a2<0)ss=(ss<<1)%mod; 154 ans=(ans+ss)%mod; 155 if ((a1!=c[m-2])&&(a2!=c[m-1]))ans=(ans-v[p][i].se+mod)%mod; 156 } 157 } 158 } 159 printf("%d ",ans); 160 } 161 return 0; 162 }
View Code