首页 > 搜索 > BFS搜索 > HDU 4127-Flood-it!-DFS-[解题报告]HOJ
2015
04-16

HDU 4127-Flood-it!-DFS-[解题报告]HOJ

Flood-it!

问题描述 :

Flood-it is a fascinating puzzle game on Google+ platform. The game interface is like follows:
Genghis Khan the Conqueror

At the beginning of the game, system will randomly generate an N×N square board and each grid of the board is painted by one of the six colors. The player starts from the top left corner. At each step, he/she selects a color and changes all the grids connected with the top left corner to that specific color. The statement “two grids are connected” means that there is a path between the certain two grids under condition that each pair of adjacent grids on this path is in the same color and shares an edge. In this way the player can flood areas of the board from the starting grid (top left corner) until all of the grids are in same color. The following figure shows the earliest steps of a 4×4 game (colors are labeled in 0 to 5):
Genghis Khan the Conqueror

Given a colored board at very beginning, please find the minimal number of steps to win the game (to change all the grids into a same color).

输入:

The input contains no more than 20 test cases. For each test case, the first line contains a single integer N (2<=N<=8) indicating the size of game board.

The following N lines show an N×N matrix (ai,j)n×n representing the game board. ai,j is in the range of 0 to 5 representing the color of the corresponding grid.
The input ends with N = 0.

输出:

The input contains no more than 20 test cases. For each test case, the first line contains a single integer N (2<=N<=8) indicating the size of game board.

The following N lines show an N×N matrix (ai,j)n×n representing the game board. ai,j is in the range of 0 to 5 representing the color of the corresponding grid.
The input ends with N = 0.

样例输入:

2
0 0 
0 0
3
0 1 2
1 1 2
2 2 1
0

样例输出:

0
3

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4127

IDA*的好题啊。。状态数太多了。用BFS肯定会爆掉内存。而且状态也不好保存。。我一开始想的是用IDA*直接暴搞。。H()评估函数,统计剩余未被改变的颜色数目。但是代码写得太乱了。。最后删了。后面参考别人的思路,用vis[][] 记录被改变的状态。 1表示已经被改变了。2表示下次可以改变的状态。0表示其他。

下面是AC代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int map[10][10];
int vis[10][10];
int deep,n;
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
bool cheack(int x,int y){
     return x>=0&&x<n&&y>=0&&y<n;
}
void change_color(int x,int y,int color){
    for(int i=0;i<4;i++){
        int nx=x+dx[i];  int ny=y+dy[i];
        if(cheack(nx,ny)){
            if(vis[nx][ny]==1)  continue;

            if(map[nx][ny]==color){
               vis[nx][ny]=1;
               change_color(nx,ny,color);
            }
            else{
               vis[nx][ny]=2;
            }
        }
    }
}
int h(){
    int cnt=0;
    bool mark[10];
    memset(mark,false,sizeof(mark));
    for(int i=0;i<n;i++)
       for(int j=0;j<n;j++){
        if(vis[i][j]==1)  continue;
        mark[map[i][j]]=true;
    }

    for(int i=0;i<=5;i++)  if(mark[i])  cnt++;
   // printf("%d\n",cnt);
    return cnt;
}
bool  dfs(int d){
      int t=h();
      if(d==deep)     return (t==0?true:false);
      if(d+t>deep)    return false;

      for(int i=0;i<=5;i++){
         int cnt=0; int tvis[10][10];
         memcpy(tvis,vis,sizeof(vis));
         for(int j=0;j<n;j++) for(int k=0;k<n;k++){
             if(map[j][k]!=i) continue;
             if(vis[j][k]==2){
                  vis[j][k]=1;
                  change_color(j,k,i);
                  cnt++;
             }
         }
//         for(int i=0;i<n;i++){ for(int j=0;j<n;j++)
//              printf("%d ",vis[i][j]);
//              printf("\n");
//         }
      //   system("pause");
         if(cnt>0&&dfs(d+1))  return true;
         memcpy(vis,tvis,sizeof(tvis));
      }
      return false;
}
int main(){

    while(scanf("%d",&n)!=EOF,n){
        for(int i=0;i<n;i++) for(int j=0;j<n;j++) {
         scanf("%d",&map[i][j]);
        }
        memset(vis,0,sizeof(vis));
        deep=0;  vis[0][0]=1;
        change_color(0,0,map[0][0]);
//         for(int i=0;i<n;i++){ for(int j=0;j<n;j++)
//              printf("%d ",vis[i][j]);
//              printf("\n");
//         }
        while(true){
           if(dfs(0)) break;
            deep++;
         }
        printf("%d\n",deep);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/w00w12l/article/details/7904475


, ,
  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  3. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }