二分搜索+DFS

题目大意：给一个 n*n 的迷宫，迷宫每一格有一个整数表示该点的难度值，求从（1，1）到（n，n）的所用路径中，难度差最小是多少。

[cpp]
include<stdio.h>
#include<string.h>
#define N 101
#define INF 0x7fffffff
int map[N][N],visit[N][N];
int n,H,L,flag;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
void DFS(int x,int y)
{
    int i,next_x,next_y;
    if(flag)return ;
    visit[x][y]=1;
    if(map[x][y]<L || map[x][y]>H)
        return ;
    if(x==n && y==n){
        flag=1;
        return;
    }
    for(i=0;i<4;i++){
        next_x=x+dir[i][0];
        next_y=y+dir[i][1];
        if(next_x>=1 && next_x<=n && next_y>=1 && next_y<=n && !visit[next_x][next_y]){
            DFS(next_x,next_y);
        }
    }
}
int main()
{
    int i,j;
    int max,min;
    int hight,mid,low;
    while(scanf("%d",&n)!=EOF){
        min=INF;
        max=-1;
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                scanf("%d",&map[i][j]);
                if(map[i][j]<min)min=map[i][j];
                if(map[i][j]>max)max=map[i][j];
            }
        }
        hight=max-min;
        low=0;
        while(hight>=low){
            mid=(hight+low)/2;
            for(i=min;i<=max-mid;i++){
                H=i+mid;L=i;flag=0;//搜索范围[L,H](即[i,i+mid]),区间长度为mid，mid越大搜索范围越大
                memset(visit,0,sizeof(visit));
                DFS(1,1);
                if(flag)break;
            }
            if(i<=max-mid)hight=mid-1;//当前范围内能找到，mid变小，缩小搜索范围；
            else low=mid+1;//当前范围内找不到，扩大搜索范围；
        }
        printf("%d\n",hight+1);
    }
    return 0;
}

#include<stdio.h>
#include<string.h>
#define N 101
#define INF 0x7fffffff
int map[N][N],visit[N][N];
int n,H,L,flag;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
void DFS(int x,int y)
{
int i,next_x,next_y;
if(flag)return ;
visit[x][y]=1;
if(map[x][y]<L || map[x][y]>H)
  return ;
if(x==n && y==n){
  flag=1;
  return;
}
for(i=0;i<4;i++){
  next_x=x+dir[i][0];
  next_y=y+dir[i][1];
  if(next_x>=1 && next_x<=n && next_y>=1 && next_y<=n && !visit[next_x][next_y]){
   DFS(next_x,next_y);
  }
}
}
int main()
{
int i,j;
int max,min;
int hight,mid,low;
while(scanf("%d",&n)!=EOF){
  min=INF;
  max=-1;
  for(i=1;i<=n;i++){
   for(j=1;j<=n;j++){
    scanf("%d",&map[i][j]);
    if(map[i][j]<min)min=map[i][j];
    if(map[i][j]>max)max=map[i][j];
   }
  }
  hight=max-min;
  low=0;
  while(hight>=low){
   mid=(hight+low)/2;
   for(i=min;i<=max-mid;i++){
    H=i+mid;L=i;flag=0;//搜索范围[L,H](即[i,i+mid]),区间长度为mid，mid越大搜索范围越大
    memset(visit,0,sizeof(visit));
    DFS(1,1);
    if(flag)break;
   }
   if(i<=max-mid)hight=mid-1;//当前范围内能找到，mid变小，缩小搜索范围；
   else low=mid+1;//当前范围内找不到，扩大搜索范围；
  }
  printf("%d\n",hight+1);
}
return 0;
}

补充：软件开发 , C++ ,