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

最近准备开始刷题了，不知道能坚持多久。
第一道，枚举，之前就见到过，昨天才写ac，方法一是枚举+dfs，也是最好理解的方法。方法二是位运算+bfs，对于我这个不太会位运算的，看的有点难受。

#include<iostream>#include<set>#include<queue>#include<cmath>#include<stack>#include<vector>#include<string>#include<cstring>#include<cstdio>#include<algorithm>#include<functional>using namespace std;const int maxn=6;const int INF=0x3f3f3f3f;int minn=INF,dir[5][2]={   0,0,0,1,1,0,0,-1,-1,0};char str[5][5];bool check(){       char c=str[0][0];    for(int i=0;i<4;i++){           for(int j=0;j<4;j++){               if(str[i][j]!=c) return 0;        }    }    return 1;}void swapp(int x,int y){       for(int i=0;i<5;i++){           int xx=x+dir[i][0];        int yy=y+dir[i][1];        if(xx<0||xx>=4||yy<0||yy>=4) continue;        if(str[xx][yy]=='w') str[xx][yy]='b';        else if(str[xx][yy]='b') str[xx][yy]='w';    }}void dfs(int x,int y,int step){       if(step>16) return ;    if(check()){           if(step<minn) minn=step;        return ;    }    if(y>=4){           x++;        y=0;    }    if(x>=4) return ;    for(int i=0;i<2;i++){           if(i==0){               swapp(x,y);            dfs(x,y+1,step+1);            swapp(x,y);//把翻过去的点恢复到没翻之前的状态        }else{               dfs(x,y+1,step);        }    }}int main(){       for(int i=0;i<4;i++){           scanf("%s",str[i]);    }    dfs(0,0,0);    if(minn<=16) printf("%d\n",minn);    else printf("Impossible\n");    return 0;}

我这个就写给自己看看，要想看详细的，去找那种带注释的代码，我是一边写一边理解的。
检查函数：检查是否已经是只有黑或只有白
翻转函数：判断边界，在边界内，上下左右翻转。
DFS：从(0,0)开始，每个位置都翻一下，分两种翻，不翻，然后检查，在每个点的操作下操作下一个点，然后不断的step++，找到那个最小的step，就是答案，最小翻转次数。
我唯一加了注释的地方，让我更加理解了dfs的递归思想，翻过去的情况接着走，都压栈中，然后每种情况走到，走到头了都是一种颜色了，更新minn，要不就走到头，就是十六个点都检查过了，返回，从栈中取情况回来，然后把栈中的情况实现完。翻过去在翻回来，为了这种情况对下种情况没有影响。

bfs自己没写出来，看了别人的也是一拖再拖，搞得不是太懂，没法自己写出来，位运算还要在理解，过几天补，先搞下一题。

转载地址：http://zhdr.baihongyu.com/