程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu1010 Tempter of the Bone(dfs+奇偶剪枝)

hdu1010 Tempter of the Bone(dfs+奇偶剪枝)

編輯:C++入門知識

hdu1010 Tempter of the Bone(dfs+奇偶剪枝)


 

第二次做這個題目了,結果沒仔細讀題,直接就BFS了, 原來是求是否恰好在T 秒逃出迷宮, 而不是T秒內;

上次做是在剛學習搜索的時候,看樣子印象還是不夠深刻,奇偶剪枝也忘得差不多了,故在寫一篇博客;

先介紹一下奇偶剪枝,

 

 

首先舉個例子,有如下4*4的迷宮,'.'為可走路段,'X'為障礙不可通過

S...
....
....
...D

從S到D的最短距離為兩點橫坐標差的絕對值+兩點縱坐標差的絕對值 = abs(Sx - Dx) + abs(Sy - Dy) = 6,這個應該是顯而易見的。

遇到有障礙的時候呢

S.XX
X.XX
...X
...D

你會發現不管你怎麼繞路,最後從S到達D的距離都是最短距離+一個偶數,這個是可以證明的

而我們知道:

奇數 + 偶數 = 奇數
偶數 + 偶數 = 偶數

因此不管有多少障礙,不管繞多少路,只要能到達目的地,走過的距離必然是跟最短距離的奇偶性是一致的。

以上轉自博主:Enstein_jun

所以對於本題而言,設MinDistance =abs(Sx - Dx) + abs(Sy - Dy); 本題給的時間T ;

只要 MinDistance-T 是偶數則能夠到達,是奇數就直接捨棄了 ;

【AC代碼】

 

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n,m,t;
char map[10][10];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int stx,sty,endx,endy;
struct co
{
    int x,y;
    int step;
};
bool dfs(co a)
{
    co b;
    if(a.x==endx&&a.y==endy&&a.step==t)
        return true;
    for(int i=0;i<4;i++)
    {
        b.x=a.x+dx[i];
        b.y=a.y+dy[i];
        b.step=a.step+1;
        if(b.x<0||b.y<0||b.x>n-1||b.y>m-1||map[b.x][b.y]=='X'||b.step>t)
            continue;
        else
        {
            map[b.x][b.y]='X';
            if(dfs(b))
                return true;
            else
            {
                map[b.x][b.y]='.';
                continue;
            }
        }
    }
    return false;
}
int main()
{
    while(cin>>n)
    {
        cin>>m>>t;
        if(n==0)
            break;
        for(int i=0;i>map[i][j];
                if(map[i][j]=='S')
                {
                    stx=i;sty=j;
                }
                if(map[i][j]=='D')
                {
                    endx=i;endy=j;
                }
            }
        }
        int ans=(abs(stx-endx)+abs(sty-endy)-t) ;//奇偶剪枝
        if( ans%2)
            cout<

 

後來參照了大神的代碼,發現他們能不用剪枝,就能將時間優化到500ms;

【大神代碼】

 

#include 
#include 
#include 
using namespace std;
char maze[10][10];
bool dfs(int x, int y, int T){
    // 剩一步時即可判斷是否為出口,找到返回true
    if (T == 1){
        if (maze[x-1][y] == 'D') return true;
        if (maze[x+1][y] == 'D') return true;
        if (maze[x][y-1] == 'D') return true;
        if (maze[x][y+1] == 'D') return true;
        return false;
    }
    else{
        // 標記走過
        maze[x][y] = 'X';
        // 深度優先搜索
        if (maze[x-1][y] == '.' && dfs(x-1, y, T-1)) return true; 
        if (maze[x+1][y] == '.' && dfs(x+1, y, T-1)) return true;
        if (maze[x][y-1] == '.' && dfs(x, y-1, T-1)) return true;
        if (maze[x][y+1] == '.' && dfs(x, y+1, T-1)) return true;
        // 還原走過
        maze[x][y] = '.';
        return false;
    }
}
int main(){
    int sx,sy,gx,gy;
    int N,M,T;
    while(cin>>N>>M>>T,T){
        memset(maze,'X',sizeof(maze));
        for(int i=0;i>maze[i][j];
                if(maze[i][j]=='S')
                    sx=i,sy=j;
                else if(maze[i][j]=='D')
                    gx=i,gy=j;
            }
        }
       // if( ( abs(sx-gx)+abs(sy-gy) - T ) & 1 )
        //奇偶剪枝
         //   cout<

 

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