POJ 3279 DFS-白红宇

POJ 3279 DFS

阅读量：5878 次

发布时间：2019-06-19

本文共 2642 字，大约阅读时间需要 8 分钟。

题意

农夫让牛在田里踩砖块，每一块砖块有黑白两面，每被踩一下，就可以翻一面（白变黑，黑变白），然而牛的脚比较大，每次踩块都会踩到邻近的4块。现在告诉你砖块组成了N＊M的图，问奶牛最少踩几下，可以把所有砖块都变白。如果有解一样大的，就选取字典序最小的。

分析

就给出一个N＊M的01矩阵，变换规则如题意所示，问最少几次能够形成全0矩阵，并输出方式。如果多个解次数一样，选区字典序最小的。

需要进行枚举，如果我们对第一行的变换状态进行枚举，后面的状态就都能确定。因为当我们变换k行的时候，我们一定要保证，变换完k行后，k－1行一定要是全0的，不然，我们再也无法使k－1行变为0。所以如果确定了第一行的变换，整个图的变换就能够一定确定下来。

枚举第一行变换状态的时候，要求字典序最小，那我们就枚举二进制数一样，0000 ， 0001 ，0010 这样枚举第一行。纪录最小答案。

其实可以用for解决，但是写dfs也可以。

代码

1 /* When all else is lost the future still remains. */ 2 /* You can be the greatest */ 3 #define rep(X,Y,Z) for(int X=(Y);X<(Z);X++) 4 #define drep(X,Y,Z) for(int X=(Y);X>=(Z);X--) 5 #define fi first 6 #define se second 7 #define mk(X,Y) make_pair((X),(Y)) 8 #define inf 0x3f3f3f3f 9 #define clr(X,Y) memset(X,Y,sizeof(X))10 #define pb push_back11 //head12 #include 
     
      13 #include 
      
       14 #include 
       
        15 #include 
        
         16 #include 
         
          17 #include 
          18 #include 
           
            19 using namespace std;20 #define maxM 2021 #define maxN 2022 int dx[] = { 0,-1,0,1,0};23 int dy[] = { 0,0,-1,0,1};24 int ord[maxN][maxM];25 int cur[maxN][maxM];26 int re[maxN][maxM];27 int ansm[maxN][maxM];28 void flip(int x , int y){29 rep(i,0,5) cur[x+dx[i]][y+dy[i]] = !cur[x+dx[i]][y+dy[i]];30 }31 bool check(int line , int m){32 rep(i,1,m+1) if(cur[line][i] != 0) return 0;33 return 1;34 }35 bool dfs(int line , int n , int m){36 if(line == n + 1) return check(line - 1,m);37 drep(pos,m,1) if(cur[line-1][pos] == 1) {38 flip(line,pos);39 re[line][pos] = 1;40 }41 if(!check(line - 1,m)) return 0;42 return dfs(line + 1 , n , m);43 }44 bool change(int n , int m){45 rep(i,2,n+1) rep(j,1,m+1) re[i][j] = 0;46 rep(i,1,n+1) rep(j,1,m+1) cur[i][j] = ord[i][j];47 drep(i,m,0){48 if(i == 0) return 0;49 if(re[1][i]) continue;50 else{51 re[1][i] = 1;52 rep(j,i+1,m+1) re[1][j] = 0;53 break;54 }55 }56 rep(i,1,m+1) if(re[1][i]) flip(1,i);57 return 1;58 }59 bool slove(int n , int m){60 bool ans = 0;61 int tmin = inf;62 do{63 ans = dfs(2,n,m);64 if(ans){65 int temp = 0;66 rep(i,1,n+1) rep(j,1,m+1) temp += re[i][j];67 if(temp < tmin){68 tmin = temp;69 rep(i,1,n+1) rep(j,1,m+1) ansm[i][j] = re[i][j];70 }71 }72 }while(change(n,m));73 return tmin == inf ? 0 : 1;74 }75 int main(){76 int n , m;77 while(~scanf("%d %d",&n,&m)){78 rep(i,1,n+1) rep(j,1,m+1) scanf("%d",&ord[i][j]);79 rep(i,1,n+1) rep(j,1,m+1) cur[i][j] = ord[i][j];80 clr(re,0);81 bool ok = slove(n,m);82 if(ok) rep(i,1,n+1){83 rep(j,1,m+1){ if(j-1) printf(" "); printf("%d",ansm[i][j]);}84 printf("\n");85 }else printf("IMPOSSIBLE\n");86 87 }88 return 0;89 90 }

转载于:https://www.cnblogs.com/ticsmtc/p/5960916.html

你可能感兴趣的文章

关于Microsoft CRM 2013自动保存Autosave功能的10点说明