HDU1813:Escape from Tetris(IDA)

Problem Description

因为整日整夜地对着这个棋盘，Lele最终走火入魔。每天一睡觉。他就会梦到自己会被人被扔进一个棋盘中，一直找不到出路，然后从梦中惊醒。久而久之，Lele被搞得精神衰弱。梦境是否会成为现实，谁也说不准，只是不怕一万仅仅怕万一。如今Lele每次看到一个棋盘，都会想象一下自己被关进去以后要怎样逃生。

Lele碰到的棋盘都是正方形的，当中有些格子是坏的，不能够走，剩下的都是能够走的。仅仅要一走到棋盘的边沿（最外面的一圈）。就算已经逃脱了。Lele梦见自己一定会被扔在一个能够走的格子里。可是不确定详细是哪一个。所以他要做好被扔在随意一个格子的准备。

如今Lele请你帮忙，对于随意一个棋盘，找出一个最短的序列，序列里能够包含"north"(地图里向上),"east"(地图里向右),"south"(地图里向下),"west"(地图里向左)。这四个方向命令。

不论Lele被扔在棋盘里的哪个好的格子里。都能按这个序列行走逃出棋盘。

逃脱的详细方法是：不论Lele被扔在哪里，Lele依照序列里的方向命令一个一个地走，每一个命令走一格，假设走的时候会碰到坏的格子，则忽略这条命令。

当然。假设已经逃脱了。就能够不考虑序列中剩下的命令了。

Input

本题目包括多组測试，请处理至文件结束。

每组測试第一行包括一个正整数 N (0<N<9)，代表棋盘的大小是 N*N

接下来有N行，每行N个字符代表这个棋盘。

当中0代表该位置是好的，能够走。1代表该位置是坏的，不能够走。

题目数据保证，对于随意一个棋盘，都存在题目中所要求的序列

Output

对于每组数据，输出题目所要求的序列。序列中每一个元素一行。

假设存在两个符合要求的序列，请输出字典序最小的那个序列。

两个測试之间请用一个空行隔开。

Sample Input

Sample Output

east

north

有时候一个粗心就会银海非常久的WA啊。。。

这道题要进行几次搜索，首先先用BFS搜出每一个位置到达边界的步数，然后再用IDA去找出走法

#include <stdio.h>

#include <string.h>

#include <queue>

#include <algorithm>

using namespace std;

const int inf = 1000000000;

struct node

{

    int x,y;

};

char str[4][10] = {"east","north","south","west"};

char map[9][9];

int to[4][2] = {0,1,-1,0,1,0,0,-1};

int L,n,dis[9][9],step,path[1000];

queue<node> Q;

int onedge(int i,int j)

{

    return i==0 || j == 0 || i == n-1 || j == n-1;

}

int ismap(int i,int j)

{

    return i>=0 && i<n && j>=0 && j<n;

}

void bfs()//求出每一个点到达边界的步数

{

    int i;

    node a,next;

    while(!Q.empty())

    {

        a = Q.front();

        Q.pop();

        for(i = 0; i<4; i++)

        {

            next.x=a.x+to[i][0];

            next.y=a.y+to[i][1];

            if(!ismap(next.x,next.y)) continue;

            if(!map[next.x][next.y]) continue;

            if(dis[next.x][next.y]>dis[a.x][a.y]+1)

            {

                dis[next.x][next.y]=dis[a.x][a.y]+1;

                Q.push(next);

            }

        }

    }

}

void init()//初始化，先将边界找出，步数设置为0,

{

    int i,j,k;

    node a;

    while(!Q.empty()) Q.pop();

    for(i = 0; i<n; i++)

    {

        for(j = 0; j<n; j++)

        {

            dis[i][j] = inf;

            map[i][j] = map[i][j]=='1'?0:1;

            if(!map[i][j]) continue;

            if(onedge(i,j))

            {

                a.x = i;

                a.y = j;

                dis[i][j] = 0;

                Q.push(a);

            }

        }

    }

    bfs();

}

int get_h(char mat[9][9])//找出最大到达边界的步数

{

    int i,j,k,maxn = 0;

    for(i = 0; i<n; i++)

    {

        for(j = 0; j<n; j++)

        {

            if(mat[i][j])

                maxn = max(maxn,dis[i][j]);

        }

    }

    return maxn;

}

int IDA(char mat[9][9],int cnt)

{

    if(cnt+get_h(mat)>step) return 0;

    if(cnt == step) return 1;

    int i,x,y,tx,ty;

    char tem[9][9];

    for(i = 0; i<4; i++)

    {

        memset(tem,0,sizeof(tem));

        for(x = 0; x<n; x++)

        {

            for(y = 0; y<n; y++)

            {

                if(onedge(x,y) || !mat[x][y]) continue;

                tx = x+to[i][0];

                ty = y+to[i][1];

                if(!map[tx][ty]) tem[x][y] = 1;

                else tem[tx][ty] = 1;

            }

        }

        path[cnt] = i;

        if(IDA(tem,cnt+1)) return 1;

    }

    return 0;

}

int main()

{

    int i,j,k,flag = 0;

    while(~scanf("%d",&n))

    {

        if(flag++)

        printf("\n");

        for(i = 0; i<n; i++)

            scanf("%s",map[i]);

        init();

        step = 0;

        while(1)

        {

            if(IDA(map,0))break;

            step++;

        }

        for(i = 0; i<step; i++)

            printf("%s\n",str[path[i]]);

    }

    return 0;

}

巴特西

HDU1813:Escape from Tetris(IDA)

最新文章

热门文章