首页 > 搜索 > BFS搜索 > HDU 1813 Escape from Tetris-BFS-[解题报告] C++
2013
12-23

HDU 1813 Escape from Tetris-BFS-[解题报告] C++

Escape from Tetris

问题描述 :

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

Lele碰到的棋盘都是正方形的,其中有些格子是坏的,不可以走,剩下的都是可以走的。只要一走到棋盘的边沿(最外面的一圈),就算已经逃脱了。Lele梦见自己一定会被扔在一个可以走的格子里,但是不确定具体是哪一个,所以他要做好被扔在任意一个格子的准备。

现在Lele请你帮忙,对于任意一个棋盘,找出一个最短的序列,序列里可以包括"north"(地图里向上),"east"(地图里向右),"south"(地图里向下),"west"(地图里向左),这四个方向命令。不论Lele被扔在棋盘里的哪个好的格子里,都能按这个序列行走逃出棋盘。
逃脱的具体方法是:不论Lele被扔在哪里,Lele按照序列里的方向命令一个一个地走,每个命令走一格,如果走的时候会碰到坏的格子,则忽略这条命令。当然,如果已经逃脱了,就可以不考虑序列中剩下的命令了。

输入:

本题目包含多组测试,请处理至文件结束。
每组测试第一行包含一个正整数 N (0<N<9),代表棋盘的大小是 N*N
接下来有N行,每行N个字符代表这个棋盘。
其中0代表该位置是好的,可以走,1代表该位置是坏的,不可以走。

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

输出:

对于每组数据,输出题目所要求的序列,序列中每个元素一行。
如果存在两个符合要求的序列,请输出字典序最小的那个序列。

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

样例输入:

4
1101
0001
1100
1001

样例输出:

east
north

HDU_1813

    一种可行的思路是迭代加深搜索,在搜索的过程中按字典序依次选择四种操作,然后将所有的空格统一执行这个移动操作,如果最终所有空格都移到了边缘,那么就说明找到了最优的深度同时也找到了字典序最优的操作序列。

    在搜索的时候可以加一个有效的剪枝:先bfs预处理出每个空格移到边缘所需的最少步数,这样如果在搜索过程中发现某个空格即便按最快的方案移动都不能在迭代加深限制的步数内到达边缘的话,就可以剪枝了。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define MAXN 10
#define MAXD 40
#define INF 0x3f3f3f3f
int dx[] = {0, -1, 1, 0}, dy[] = {1, 0, 0, -1};
int N, M, g[MAXN][MAXN], ix[MAXD], iy[MAXD], dis[MAXN][MAXN];
int list[1010];
inline int inedge(int x, int y)
{
    return x == 1 || x == N || y == 1 || y == N;    
}
int bfs(int sx, int sy)
{
    int i, x, y, nx, ny, d[MAXN][MAXN];
    memset(d, -1, sizeof(d));
    std::queue <int> q;
    d[sx][sy] = 0, q.push(sx * 10 + sy);
    while(!q.empty())
    {
        x = q.front() / 10, y = q.front() % 10, q.pop();
        if(inedge(x, y)) return d[x][y];
        for(i = 0; i < 4; i ++)
        {
            nx = x + dx[i], ny = y + dy[i];
            if(g[nx][ny] && d[nx][ny] == -1)
                d[nx][ny] = d[x][y] + 1, q.push(nx * 10 + ny);    
        }    
    }
    return 0;
}
void init()
{
    int i, j;
    char b[MAXD];
    for(i = 1; i <= N; i ++)
    {
        scanf("%s", b + 1);
        for(j = 1; j <= N; j ++) g[i][j] = 1 - (b[j] - '0');    
    }
    M = 0;
    for(i = 1; i <= N; i ++)
        for(j = 1; j <= N; j ++)
        {
            if(g[i][j])
            {
                if(inedge(i, j)) dis[i][j] = 0;
                else
                {
                    dis[i][j] = bfs(i, j);
                    ix[M] = i, iy[M] = j, ++ M;
                }
            }
            else dis[i][j] = INF;
        }
}
int Max(int *x, int *y)
{
    int i, ans = 0;
    for(i = 0; i < M; i ++) ans = std::max(ans, dis[x[i]][y[i]]);
    return ans;    
}
int dfs(int d, int *ix, int *iy)
{
    if(Max(ix, iy) > d) return 0;
    if(d == 0) return 1;
    int i, j, x[MAXD], y[MAXD], nx, ny;
    for(i = 0; i < 4; i ++)
    {
        list[d] = i;
        for(j = 0; j < M; j ++)
        {
            nx = ix[j] + dx[i], ny = iy[j] + dy[i];
            if(inedge(ix[j], iy[j]) || g[nx][ny] == 0)
                x[j] = ix[j], y[j] = iy[j];
            else
                x[j] = nx, y[j] = ny;
        }
        if(dfs(d - 1, x, y)) return 1;
     }
     return 0;
}
void solve()
{
    int i, dep;
    if(M == 0) return ;
    for(dep = 1; !dfs(dep, ix, iy); dep ++);
    for(i = dep; i > 0; i --)
    {
        if(list[i] == 0) puts("east");
        else if(list[i] == 1) puts("north");
        else if(list[i] == 2) puts("south");
        else puts("west");
    }
}
int main()
{
    int t = 0;
    while(scanf("%d", &N) == 1)
    {
        init();
        if(t ++) printf("\n");
        solve();    
    }
    return 0;    
}

解题报告转自:http://www.cnblogs.com/staginner/archive/2012/08/29/2662304.html


, ,
  1. /*
    * =====================================================================================
    *
    * 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;
    }

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  3. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。