【日常学习】【迭代加深搜索】codevs1049 棋盘染色题解

逃离我推掉我的手 2022-08-02 07:27 159阅读 0赞

迭代加深什么的本来完全不会，所以代码基本是抄的黄学长的= =hzwer君

感谢里奥同学友情帮助调代码= -=

先上题目吧

题目描述 Description

有一个5×5的棋盘，上面有一些格子被染成了黑色，其他的格子都是白色，你的任务的对棋盘一些格子进行染色，使得所有的黑色格子能连成一块，并且你染色的格子数目要最少。读入一个初始棋盘的状态，输出最少需要对多少个格子进行染色，才能使得所有的黑色格子都连成一块。（注：连接是指上下左右四个方向，如果两个黑色格子只共有一个点，那么不算连接）

输入描述 Input Description

输入包括一个5×5的01矩阵，中间无空格，1表示格子已经被染成黑色。

输出描述 Output Description

输出最少需要对多少个格子进行染色

样例输入 Sample Input

11100

11000

10000

01111

11111

样例输出 Sample Output

迭代加深就是为了应对BFS空间太大或者各种不可行因素而出现的一种算法，我觉得他更多的是一种思想。原理就是限制搜索的层数，因为结果很有可能在前几层就出现了。如果这一层没有，要搜下一层，还必须从头搜起，因此比较耗时，但由于前几层搜到的可能性很大，相对深搜又节省了不少时间，同时相对广搜还节省了空间，对于状态多又可能在有限步内解决的题目不失为一种好的选择。

框架：[http://www.docin.com/p-587407856.html][http_www.docin.com_p-587407856.html]

那么，代码君~基本是黄学长的·1·

限制层数 对于每种方案搜索 然后检验是否能一次把联通的都删除完 如果能说明方案可行，直接退出输出层数。

搜索时为避免重复，采用两个循环，第一个循环是当前层，第二个循环是当前层下面的部分。请参考代码理解

//codevs1049 棋盘染色 迭代加深搜索/状压搜索
    //coded by ametake努力抄袭黄学长代码= =
    #include
       
        
    #include
        
         
    #include
         
           
    #define dfsnext(x,y,z) y==5?dfs(x+1,1,z):dfs(x,y+1,z)
    using namespace std;
    
    bool map[6][6],t[6][6],ans=0;
    int dep,xx[4]={0,0,-1,1},yy[4]={-1,1,0,0};
    
    void init()
    {
         freopen("1.txt","r",stdin);
         freopen("2.txt","w",stdout);
         
        char ch[10];
        for(int i=1;i<=5;i++)
        {
           scanf("%s",&ch);
           for(int j=1;j<=5;j++)
           map[i][j]=ch[j-1]-'0';
           }
    }
    
    void del(int x,int y)
    {
         t[x][y]=0;
         for (int i=0;i<4;i++)
         {
             int nx=x+xx[i];
             int ny=y+yy[i];
             if (nx<1||ny<1||nx>5||ny>5||!t[nx][ny]) continue;
             del(nx,ny);
         }
    }
    
    bool judans()
    {
         bool flag=0;
         for (int i=1;i<=5;i++)
         {
             for (int j=1;j<=5;j++)
             {
                 t[i][j]=map[i][j];
             }
         }
         for (int i=1;i<=5;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 dfs(int x,int y,int depth)
    {
         if (depth==dep)
         {
             if (judans()) ans=1;
             return;
         }
         if (ans!=0||x==6) return;//此时，由于有自动换行功能，如果x==6，说明已经搜索完毕
         for (int i=y;i<=5;i++)
         {
             if (map[x][i]) continue;
             map[x][i]=1;
             if(i == 5)
             {
                  dfs(x+1,1,depth+1);
                  }
             else
             {
                 dfs(x,i+1,depth+1);
                 }
             map[x][i]=0;
         } 
         for (int i=x+1;i<=5;i++)
         {
             for (int j=1;j<=5;j++)
             {
                 if (map[i][j]) continue;
                 map[i][j]=1;
                 if(j == 5)
             {
                  dfs(i+1,1,depth+1);
                  }
             else
             {
                 dfs(i,j,depth+1);
                 }
                 map[i][j]=0;
             }
         }
    }
    
    int main()
    {
        init();
        for (dep=0;dep<=25;dep++)
        {
        
            dfs(1,1,0);
            if (ans!=0) {printf("%d\n",dep);return 0;}
        }
        if (ans==0) printf("TUT");
        return 0;
    }

——请君暂上凌烟阁，若个书生万户侯

[http_www.docin.com_p-587407856.html]: http://www.docin.com/p-587407856.html