程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> NYOJ306 走迷宮(dfs+二分搜索)

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

編輯：關於C++

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

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

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

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

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

樣例輸出

題目分析：
對於每一個答案的范圍，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