程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NYOJ306 走迷宮(dfs+二分搜索)

NYOJ306 走迷宮(dfs+二分搜索)

編輯:C++入門知識

NYOJ306 走迷宮(dfs+二分搜索)



Dr.Kong設計的機器人卡多非常愛玩,它常常偷偷跑出實驗室,在某個游樂場玩之不疲。這天卡多又跑出來了,在SJTL游樂場玩個不停,坐完碰碰車,又玩滑滑梯,這時卡多又走入一個迷宮。整個迷宮是用一個N * N的方陣給出,方陣中單元格中填充了一個整數,表示走到這個位置的難度。

這個迷宮可以向上走,向下走,向右走,向左走,但是不能穿越對角線。走迷宮的取勝規則很有意思,看誰能更快地找到一條路徑,其路徑上單元格最大難度值與最小難度值之差是最小的。當然了,或許這樣的路徑不是最短路徑。

     機器人卡多現在在迷宮的左上角(第一行,第一列)而出口在迷宮的右下角(第N行,第N列)。

卡多很聰明,很快就找到了這樣的一條路徑。你能找到嗎?

輸入
有多組測試數據,以EOF為輸入結束的標志
第一行: N 表示迷宮是N*N方陣 (2≤ N≤ 100)
接下來有N行, 每一行包含N個整數,用來表示每個單元格中難度 (0≤任意難度≤120)。
輸出
輸出為一個整數,表示路徑上最高難度與和最低難度的差。
樣例輸入

5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1

樣例輸出

2

題目分析:
對於每一個答案的范圍,dfs判斷對於當前范圍值是否能否從(1,1)到達(n,n)。如果能找到某一路徑到達(n,n),則證明當前答案能夠滿足要求,還可以繼續減小。我們可以二分[0,max-min]之間的值,進行判斷即可。

AC代碼:

/**
  *@xiaoran
  *dfs+二分搜索
  *迷宮可以向上走,向下走,向右走,向左走
  *從(1,1)到(n,n)能否找到一條路徑,
  *其路徑上單元格最大難度值與最小難度值之差是最小的
  */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
/**
 *minn:地圖中的最小值,
 *maxn:地圖中的最大值,
 *flag:標記差值在某個范圍內是否能夠到達(n,n)
 *vmap[][]:地圖
 *vis[i][j]:該節點是否已被訪問
 *dx[],dy[]:搜索四個方向
 */
int n,minn,maxn,flag;
int vis[120][120],vmap[120][120];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

void Init(){
    minn=121;
    maxn=-1;
    memset(vmap,-1,sizeof(vmap));//這裡一定要賦值為小於0或者大於120的值
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf(%d,&vmap[i][j]);
            maxn=max(vmap[i][j],maxn);
            minn=min(vmap[i][j],minn);
        }
    }
}

/**
 *差值在R-L的范圍內是否存在從(1,1)-->(n,n)的路徑
 *這裡判斷的是每一值是否在[L,R]之間·
 */
void dfs(int i,int j,int L,int R){
    if(flag) return;
    if(i==n&&j==n){//能夠找到有效路徑,返回,不在搜素其他值
        flag=1; return;
    }
    for(int k=0;k<4;k++){
        int xi=i+dx[k];
        int xj=j+dy[k];
        if(vmap[xi][xj]>=L&&vmap[xi][xj]<=R&&vis[xi][xj]==0){
            //改點的值滿足條件且未被訪問。
            vis[xi][xj]=1;//這裡一定要先標記啊
            dfs(xi,xj,L,R);
        }

    }
}

/**
 *用來判斷當差值為k時,是否滿足能夠找到從(1,1)-->(n,n)的路徑
 */
int Judge(int k){
    for(int i=minn;i<=maxn-k;i++){
        flag=0;//先標記沒有合法路徑
        //因為dfs函數中沒有判斷vmap[1][1]和vmap[n][n]是否合法,這裡要特判
        if(vmap[1][1]i+k) continue;
        if(vmap[n][n]i+k) continue;


        memset(vis,0,sizeof(vis));
        vis[1][1]=1;//從(1,1)訪問
        dfs(1,1,i,i+k);
        if(flag) return 1;//可以找到有效路徑從(1,1)-->(n,n)
    }
    return 0;
}

int Get_ans(){
    int l=0,r=maxn-minn;
    while(l

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