hdu Flood-it!(IDA*算法)

 

 

Flood-it!

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1703 Accepted Submission(s): 396

Problem Description Flood-it is a fascinating puzzle game on Google+ platform. The game interface is like follows:

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):

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).


Input 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 (a_i,j)_n×n representing the game board. a_i,j is in the range of 0 to 5 representing the color of the corresponding grid.
The input ends with N = 0.

Output For each test case, output a single integer representing the minimal number of steps to win the game.

Sample Input

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

Sample Output

0
3

Source 2011 Asia Fuzhou Regional Contest
Recommend lcy | We have carefully selected several similar problems for you: 4123 4122 4124 4125 4126
題目大意：n*n的方格，每次從左上角染色，只能染色相連相同的數字，變化過之後就合成一塊，下次要變這一塊一起變成其他任意的顏色。最終要輸出最少多少步能夠變成同一個數字。 特別注意： 1、每次變只能變左上角的數字。或者已經與左上角合成一塊了就可以一起改變。 2、狀態數比較多，用bfs很顯然會爆掉，，第一次做IDA*搜索題目。首先，和左上角在一個連通塊的將vis標記為1，其次，和連通塊的顏色不同，但是相鄰的，標記為2，下次可以可改變的顏色。 3、估價函數，用來計算最理想狀態下的最優值。
詳見代碼。

#include 
#include 
#include 
#include 

using namespace std;

int dir[4][2]= {1,0,-1,0,0,1,0,-1};
int n;
int a[10][10],vis[10][10],want,vv[10][10];
int kk=0;

void checkcolor(int x,int y,int color)
{
    //cout<<11111<=n||Y<0||Y>=n||vv[X][Y]==1)
        {
            continue;
        }
        if (a[X][Y]==color||vis[X][Y]==1)  //如果顏色相同就將Vis標記為1
        {
            vv[X][Y]=vis[X][Y]=1;  //標記為相連
            checkcolor(X,Y,color);  //繼續搜，直到沒有相同顏色
        }
        else
            vis[X][Y]=2;  //到不相同的顏色，直接標記為相鄰
    }
}

int get_cnt(int color)//將相同顏色的方塊連通起來
{
    int t=0;
    for (int i=0; iwant)//如果我已經走的步數+估價函數中最好的值>我想要的，那就直接return。
        return false;
    if (dep==want)//如果找到我已經走的等於我的想要的就ok
        return true;
    for (int i=0; i<6; i++)
    {
        int tmp[10][10];
        memcpy(tmp,vis,sizeof(vis));
        if (get_cnt(i))//判斷當前顏色是否可以相連，合並到左上角一個塊中
        {
            memset(vv,0,sizeof(vv));
            checkcolor(0,0,i);
            if (IDA(dep+1))
               {
                   return true;
               }
        }
        memcpy(vis,tmp,sizeof(vis));
    }
    return false;
}

int main()
{
    while (~scanf(%d,&n))
    {
        if (n==0)
            break;
        for (int i=0; i