「CODEVS1050」棋盘染色 2
题目描述 Description
有一个5*N的棋盘，棋盘中的一些格子已经被染成了黑色，你的任务是对最少的格子染色，使得所有的黑色能连成一块。
输入描述 Input Description
第一行一个整数N(<=100)，接下来N行每行一个长度为5的01串，1表示所在格子已经被染成了黑色，0表示所在格子没有被染色。
输出描述 Output Description
第一行一个整数N(<=100)，接下来N行每行一个长度为5的01串，1表示所在格子已经被染成了黑色，0表示所在格子没有被染色。
样例输入 Sample Input
5 11100 11000 10000 01111 11111
样例输出 Sample Output
1
代码
按照上一题迭代深搜果断T，六七十分貌似
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<iostream> #include<cstdio> #include<cstring> #define searchnext(x,y,k) y==5? search(x+1,1,k):search(x,y+1,k) using namespace std; bool mp[101][6],t[101][6],ans; int s,xx[4]={0,0,-1,1},yy[4]={-1,1,0,0},n; void del(int x,int y) { t[x][y]=0; for(int i=0;i<4;i++) { int nowx=x+xx[i],nowy=y+yy[i]; if(nowx>5||nowy>5||nowx<1||nowy<1||!t[nowx][nowy])continue; del(nowx,nowy); } } bool judans() { bool flag=0; for(int i=1;i<=n;i++) for(int j=1;j<=5;j++) t[i][j]=mp[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=5;j++) { if(t[i][j]) { if(!flag){del(i,j);flag=1;} else return 0; } } return 1; } void search(int x,int y,int k) { if(k==s){if(judans())ans=1;return;} if(ans||x==n+1)return; for(int i=y;i<=5;i++){ if(mp[x][i])continue; mp[x][i]=1; searchnext(x,i,k+1); mp[x][i]=0; } for(int i=x+1;i<=n;i++) for(int j=1;j<=5;j++){ if(mp[i][j])continue; mp[i][j]=1; searchnext(i,j,k+1); mp[i][j]=0; } } int main() { scanf("%d",&n); char ch[10]; for(int i=1;i<=n;i++) { scanf("%s",ch); for(int j=1;j<=5;j++) mp[i][j]=ch[j-1]-'0'; } for(s=0;s<=25;s++) {search(1,1,0);if(ans){printf("%d\n",s);return 0;}} } |
状压不会写。。
计数器 9851998
OI 课件=>
OI 课件=>
另求一波codevs boss单挑战题解
求填坑，装压啊…
求补状压。。