题目描述&＃xff1a;
数据范围&＃xff1a;2<&＃61;n,m<&＃61;8
题解&＃xff1a;
很明显需要状压。但是怎么压不知道&＃xff0c;压什么不知道。
然后从条件下手。
条件1要求黑色在一起白色在一起&＃xff0c;记录轮廓线很容易做到。
条件2要求不能出现$2*2$的同色方格。我们还需要再记录当前位置的左上角。
所以这道题的轮廓线长这样。
丑图。
我们需要确定一个顺序记录哪几块互相联通。由于轮廓线奇特的形状我决定这样标号。
如果编号相同但是并不互相联通我们可以知道他俩不同颜色。
为了颜色我们决定记录某个块的颜色&＃xff0c;这样可以得到所有颜色。
于是这道题表中存的就是$1$号颜色&＃43;所有状态。
为了方便调试我用了十进制。
每次调用时都要解压&＃xff0c;处理后压缩放回去。
由于第一行和第一列找不到长这样的轮廓线&＃xff0c;我们可以搜出第一行所有状态&＃xff0c;处理第一列时直接枚举黑色/白色。
接下来就是精彩的特判环节。
&＃xff08;这一部分针对处于中心部位的一干普通点&＃xff09;
以填黑色为例。
如果这里不能填黑&＃xff1a;
1.输入要求白色。
2.拐角处已经有三个黑块。
3.要考虑到上图中红块填上后$5$号块就不再与不定颜色相邻&＃xff0c;我们不能把$5$号块憋死我们要判断$5$号是否有与之联通的好朋友在轮廓线上。
类似围棋中的气。
如果没有而且$5$号是白的&＃xff0c;那么就不能填黑&＃xff01;
等等好像是错的。
如果红块已经到$(n,m-1)$或者是$(n,m)$&＃xff0c;而且轮廓线上其他都是黑的&＃xff0c;我们可以放黑色。
所以这又是个特判。
4.对于3我们考虑的是上下断开&＃xff0c;能否出现左右断开&＃xff1f;
当然可能。
但是只能在最后一行出现。
所以统计答案时要填回去看一眼。
真 恶心。
深思熟虑后糊上去的代码&＃xff1a;
#include
#include
#include
using namespace std;
#define N 15
#define ll long long
int T,n,m,k,a[N][N];
char ch[N][N];
ll bas[N],ans;
struct Map
{int hed[1000050],cnt[2];struct EG{int nxt;ll to,w;}e[2000050][2];void ae(int f,ll t,ll w){e[&＃43;&＃43;cnt[k]][k].to &＃61; t;e[cnt[k]][k].nxt &＃61; hed[f];e[cnt[k]][k].w &＃61; w;hed[f] &＃61; cnt[k];}void push(ll u,ll w){for(int j&＃61;hed[u%1000000];j;j&＃61;e[j][k].nxt)if(e[j][k].to&＃61;&＃61;u){e[j][k].w &＃43;&＃61; w;return ;}ae(u%1000000,u,w);}void clear(){cnt[k] &＃61; 0;memset(hed,0,sizeof(hed));}
}mp;
int col[N],grp[N],tmp[N],las[N];
ll zip()
{ll ret &＃61; 0;for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)ret&＃61;10*(ret&＃43;grp[i]);return ret&＃43;col[1];
}
void upz(ll u)
{memset(tmp,-1,sizeof(tmp));tmp[1]&＃61;u%10;u/&＃61;10;for(int i&＃61;m&＃43;1;i>&＃61;1;i--,u/&＃61;10)grp[i]&＃61;u%10;for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)if(tmp[grp[i]]&＃61;&＃61;-1)tmp[grp[i]]&＃61;tmp[grp[i-1]]^1;for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)col[i]&＃61;tmp[grp[i]];
}
void shake()//get the express
{memset(tmp,0,sizeof(tmp));for(int cnt&＃61;0,i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)if(!tmp[grp[i]])tmp[grp[i]]&＃61;&＃43;&＃43;cnt;for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)grp[i]&＃61;tmp[grp[i]];
}
bool find_friend(int now,int beg,int ens)
{int cnt &＃61; 0;for(int i&＃61;beg;i<&＃61;ens;i&＃43;&＃43;)if(grp[i]&＃61;&＃61;now)cnt&＃43;&＃43;;return cnt>0;
}
bool ck1()
{for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;)if(col[i]&＃43;a[1][i]&＃61;&＃61;1)return 0;return 1;
}
bool ck2()
{int cnt &＃61; 0;for(int i&＃61;2;i<&＃61;m;i&＃43;&＃43;)cnt&＃43;&＃61;(col[i]!&＃61;col[i-1]);return cnt<&＃61;2;
}
int ck3(int c)
{if(col[m-1]&＃61;&＃61;col[m]&&col[m]&＃61;&＃61;col[m&＃43;1]&&col[m&＃43;1]&＃61;&＃61;c)return 0;int c0 &＃61; col[m],ret&＃61;1;for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)las[i]&＃61;grp[i];col[m] &＃61; c;grp[m] &＃61; m&＃43;2;if(col[m-1]&＃61;&＃61;c){int kg &＃61; grp[m-1];for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)if(grp[i]&＃61;&＃61;kg)grp[i]&＃61;m&＃43;2;}if(col[m&＃43;1]&＃61;&＃61;c){int kg &＃61; grp[m&＃43;1];for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)if(grp[i]&＃61;&＃61;kg)grp[i]&＃61;m&＃43;2;}shake();for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)if(grp[i]>2)ret &＃61; 0;for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)grp[i] &＃61; las[i];if(col[m-1]&＃61;&＃61;c){int kg &＃61; grp[m-1];for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)if(grp[i]&＃61;&＃61;kg)grp[i]&＃61;m&＃43;2;}if(col[m&＃43;1]&＃61;&＃61;c){int kg &＃61; grp[m&＃43;1];for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)if(grp[i]&＃61;&＃61;kg)grp[i]&＃61;m&＃43;2;}shake();for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)if(grp[i]>2)ret &＃61; 0;for(int i&＃61;1;i<&＃61;m&＃43;1;i&＃43;&＃43;)grp[i]&＃61;las[i];col[m] &＃61; c0;return ret;
}
void PushF()
{for(int i&＃61;0;i<(1<
}
bool check_b(int i,int j)
{if(a[i][j]&＃61;&＃61;0)return 0;if(col[j-1]&＃61;&＃61;1&&col[j]&＃61;&＃61;1&&col[j&＃43;1]&＃61;&＃61;1)return 0;if((i!&＃61;n||j!&＃61;m)&&(i!&＃61;n||j!&＃61;m-1))if(col[j&＃43;1]&＃61;&＃61;0&&!find_friend(grp[j&＃43;1],j&＃43;2,m&＃43;1)&&!find_friend(grp[j&＃43;1],1,j-1))return 0;return 1;
}
bool check_w(int i,int j)
{if(a[i][j]&＃61;&＃61;1)return 0;if(col[j-1]&＃61;&＃61;0&&col[j]&＃61;&＃61;0&&col[j&＃43;1]&＃61;&＃61;0)return 0;if((i!&＃61;n||j!&＃61;m)&&(i!&＃61;n||j!&＃61;m-1))if(col[j&＃43;1]&＃61;&＃61;1&&!find_friend(grp[j&＃43;1],j&＃43;2,m&＃43;1)&&!find_friend(grp[j&＃43;1],1,j-1))return 0;return 1;
}
int main()
{
// freopen("tt.in","r",stdin);scanf("%d",&T);bas[0]&＃61;1;for(int i&＃61;1;i<&＃61;10;i&＃43;&＃43;)bas[i] &＃61; 10*bas[i-1];while(T--){scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%s",ch[i]&＃43;1);for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){if(ch[i][j]&＃61;&＃61;&＃39;o&＃39;)a[i][j]&＃61;0;else if(ch[i][j]&＃61;&＃61;&＃39;#&＃39;)a[i][j]&＃61;1;else a[i][j]&＃61;2;}}ans&＃61;0,k&＃61;0,mp.clear();PushF();for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;){k^&＃61;1;mp.clear();for(int j&＃61;1;j<&＃61;mp.cnt[!k];j&＃43;&＃43;){ll now &＃61; mp.e[j][!k].to,val &＃61; mp.e[j][!k].w;upz(now);for(int o&＃61;m&＃43;1;o>&＃61;2;o--)grp[o]&＃61;grp[o-1],col[o]&＃61;col[o-1];for(int q&＃61;1;q<&＃61;m&＃43;1;q&＃43;&＃43;)las[q]&＃61;grp[q];if(a[i][1]!&＃61;0)//black
{if(col[2]&＃61;&＃61;1){col[1]&＃61;1,grp[1]&＃61;grp[2];shake();mp.push(zip(),val);}else{if(find_friend(grp[2],3,m&＃43;1)){col[1]&＃61;1,grp[1]&＃61;m&＃43;2;shake();mp.push(zip(),val);}else if(i&＃61;&＃61;n&&m&＃61;&＃61;2){col[1]&＃61;1,grp[1]&＃61;m&＃43;2;shake();mp.push(zip(),val);}}}for(int q&＃61;1;q<&＃61;m&＃43;1;q&＃43;&＃43;)grp[q]&＃61;las[q];if(a[i][1]!&＃61;1)//white
{if(col[2]&＃61;&＃61;0){col[1]&＃61;0,grp[1]&＃61;grp[2];shake();mp.push(zip(),val);}else{if(find_friend(grp[2],3,m&＃43;1)){col[1]&＃61;0,grp[1]&＃61;m&＃43;2;shake();mp.push(zip(),val);}else if(i&＃61;&＃61;n&&m&＃61;&＃61;2){col[1]&＃61;0,grp[1]&＃61;m&＃43;2;shake();mp.push(zip(),val);}}}}for(int j&＃61;2;j<&＃61;m;j&＃43;&＃43;){k^&＃61;1,mp.clear();for(int o&＃61;1;o<&＃61;mp.cnt[!k];o&＃43;&＃43;){ll now &＃61; mp.e[o][!k].to,val &＃61; mp.e[o][!k].w;upz(now);int c0 &＃61; col[j];if(i&＃61;&＃61;n&&j&＃61;&＃61;m){if(n&＃61;&＃61;2&&m&＃61;&＃61;2){if(col[1]&＃61;&＃61;col[3]){if((a[n][m]&＃61;&＃61;2||a[n][m]!&＃61;col[1])&&col[2]&＃61;&＃61;col[1])ans&＃43;&＃61;val*ck3(col[1]^1);else if((a[n][m]&＃61;&＃61;2||a[n][m]&＃61;&＃61;col[1])&&col[2]!&＃61;col[1])ans&＃43;&＃61;val*ck3(col[1]);}else{if(a[n][m]&＃61;&＃61;2)ans&＃43;&＃61;val*(ck3(0)&＃43;ck3(1));else ans&＃43;&＃61;val*ck3(a[n][m]);}}else{if(col[m-1]&＃61;&＃61;col[m&＃43;1]){if(a[n][m]&＃61;&＃61;2||a[n][m]&＃61;&＃61;col[m-1])ans&＃43;&＃61;val*ck3(col[m-1]);}else{if(a[n][m]&＃61;&＃61;2)ans&＃43;&＃61;val*(ck3(0)&＃43;ck3(1));else ans&＃43;&＃61;val*ck3(a[n][m]);}}continue;}if(check_b(i,j))//black
{col[j]&＃61;1;grp[j]&＃61;m&＃43;2;for(int q&＃61;1;q<&＃61;m&＃43;1;q&＃43;&＃43;)las[q]&＃61;grp[q];if(col[j-1]&＃61;&＃61;1){int kg &＃61; grp[j-1];for(int q&＃61;1;q<&＃61;m&＃43;1;q&＃43;&＃43;)if(grp[q]&＃61;&＃61;kg)grp[q]&＃61;m&＃43;2;}if(col[j&＃43;1]&＃61;&＃61;1){int kg &＃61; grp[j&＃43;1];for(int q&＃61;1;q<&＃61;m&＃43;1;q&＃43;&＃43;)if(grp[q]&＃61;&＃61;kg)grp[q]&＃61;m&＃43;2;}shake();if(i&＃61;&＃61;n&&j&＃61;&＃61;m)ans&＃43;&＃61;val;mp.push(zip(),val);for(int q&＃61;1;q<&＃61;m&＃43;1;q&＃43;&＃43;)grp[q]&＃61;las[q];}col[j] &＃61; c0;if(check_w(i,j))//white
{col[j]&＃61;0;grp[j]&＃61;m&＃43;2;if(col[j-1]&＃61;&＃61;0){int kg &＃61; grp[j-1];for(int q&＃61;1;q<&＃61;m&＃43;1;q&＃43;&＃43;)if(grp[q]&＃61;&＃61;kg)grp[q]&＃61;m&＃43;2;}if(col[j&＃43;1]&＃61;&＃61;0){int kg &＃61; grp[j&＃43;1];for(int q&＃61;1;q<&＃61;m&＃43;1;q&＃43;&＃43;)if(grp[q]&＃61;&＃61;kg)grp[q]&＃61;m&＃43;2;}shake();if(i&＃61;&＃61;n&&j&＃61;&＃61;m)ans&＃43;&＃61;val;mp.push(zip(),val);}}}}printf("%lld\n",ans);}return 0;
}
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号