程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 1813(IDA*算法+dfs)

hdu 1813(IDA*算法+dfs)

編輯:關於C++

 

 

Escape from Tetris

Time Limit: 12000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1078 Accepted Submission(s): 274

Problem Description 由於整日整夜地對著這個棋盤,Lele終於走火入魔。每天一睡覺,他就會夢到自己會被人被扔進一個棋盤中,一直找不到出路,然後從夢中驚醒。久而久之,Lele被搞得精神衰弱。夢境是否會成為現實,誰也說不准,不過不怕一萬只怕萬一。現在Lele每次看到一個棋盤,都會想象一下自己被關進去以後要如何逃生。

Lele碰到的棋盤都是正方形的,其中有些格子是壞的,不可以走,剩下的都是可以走的。只要一走到棋盤的邊沿(最外面的一圈),就算已經逃脫了。Lele夢見自己一定會被扔在一個可以走的格子裡,但是不確定具體是哪一個,所以他要做好被扔在任意一個格子的准備。

現在Lele請你幫忙,對於任意一個棋盤,找出一個最短的序列,序列裡可以包括north(地圖裡向上),east(地圖裡向右),south(地圖裡向下),west(地圖裡向左),這四個方向命令。不論Lele被扔在棋盤裡的哪個好的格子裡,都能按這個序列行走逃出棋盤。
逃脫的具體方法是:不論Lele被扔在哪裡,Lele按照序列裡的方向命令一個一個地走,每個命令走一格,如果走的時候會碰到壞的格子,則忽略這條命令。當然,如果已經逃脫了,就可以不考慮序列中剩下的命令了。

Input 本題目包含多組測試,請處理至文件結束。
每組測試第一行包含一個正整數 N (0 接下來有N行,每行N個字符代表這個棋盤。
其中0代表該位置是好的,可以走,1代表該位置是壞的,不可以走。

題目數據保證,對於任意一個棋盤,都存在題目中所要求的序列

Output 對於每組數據,輸出題目所要求的序列,序列中每個元素一行。
如果存在兩個符合要求的序列,請輸出字典序最小的那個序列。

兩個測試之間請用一個空行隔開。

Sample Input
4
1101
0001
1100
1001

Sample Output
east
north

Author linle
Source HDOJ 2007 Summer Exercise(2)
Recommend lcy | We have carefully selected several similar problems for you: 1560 1667 1043 1401 2517
題目大意:給一個n*n的棋牌,0可以走,1不可以走,可以上下左右四個方向走,最終輸出滿足條件的序列。 特別注意: 1、只要逃到棋盤的邊緣(最外面一圈)就算已經逃脫。 2、如果存在兩個符合要求的序列,請輸出字典序最小的那個序列。 3、不要出現PE
詳見代碼。
#include 
#include 
#include 
#include 
#define INF 1<<30
using namespace std;

int dir[4][2]= {0,1,-1,0,1,0,0,-1};
int n,minval[10][10];//表示每個點到邊距的最短距離
char str[10][10];
int k,want;
char dd[4][10] = {east,north,south,west};
int route[1000];//用來存路徑

struct node
{
    int x;
    int y;
} s;
queueq,qq;
void bfs()//找到每個點到底邊界的步數
{
    node ss;

    //q.push(s);
    while (!q.empty())
    {
        s=q.front();
        q.pop();
        for (int i=0; i<4; i++)
        {
            ss.x=s.x+dir[i][0];
            ss.y=s.y+dir[i][1];
            if (ss.x<0||ss.x>=n||ss.y<0||ss.y>=n)
                continue;
            if(!str[ss.x][ss.y])
                continue;
            if (minval[ss.x][ss.y]>minval[s.x][s.y]+1)
            {
                minval[ss.x][ss.y]=minval[s.x][s.y]+1;
                q.push(ss);
            }
        }
    }
}

int get_h(char s[10][10])
{
    int mab=0;
    for (int i=0; iwant)
        return false;
    if (dep==want)
        return true;
    char tmp[10][10];
    for (int i=0; i<4; i++)
    {
        memset(tmp,0,sizeof(tmp));
        for (int x=0; x

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved