当前位置：网站首页>nyoj306 走迷宫(搜索+二分)

nyoj306 走迷宫(搜索+二分)

2022-08-09 08:10:00 【51CTO】

走迷宫

1000 ms | 内存限制： 65535

Dr.Kong设计的机器人卡多非常爱玩，它常常偷偷跑出实验室，在某个游乐场玩之不疲。这天卡多又跑出来了，在SJTL游乐场玩个不停，坐完碰碰车，又玩滑滑梯，这时卡多又走入一个迷宫。整个迷宫是用一个N * N的方阵给出，方阵中单元格中填充了一个整数，表示走到这个位置的难度。

这个迷宫可以向上走，向下走，向右走，向左走，但是不能穿越对角线。走迷宫的取胜规则很有意思，看谁能更快地找到一条路径，其路径上单元格最大难度值与最小难度值之差是最小的。当然了，或许这样的路径不是最短路径。

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

卡多很聪明，很快就找到了这样的一条路径。你能找到吗？

有多组测试数据，以EOF为输入结束的标志

第一行： N 表示迷宫是N*N方阵 (2≤ N≤ 100)

接下来有N行，每一行包含N个整数，用来表示每个单元格中难度 (0≤任意难度≤120)。

输出输出为一个整数，表示路径上最高难度与和最低难度的差。样例输入

样例输出

来源第四届河南省程序设计大赛

上传者张云聪

这种思路的确是没想到

由于这道题的难度范围是0-120 可以对难度二分的方法

也就是找到一个确定的难度,然后根据难度搜索，就能大大减少搜索的次数

如果我们能根据难度找到一条符合条件的路，那么就可以通过二分法继续缩小难度的范围来继续查找。直到找到最小。

       
       #include <stdio.h>
       
       #include <string.h>
       
       #include <algorithm>
       
       using 
       
       namespace 
       
       std;
       
       #define INF 0X3FFFFFFF 
       
       int 
       
       map[
       
       105][
       
       105];
       
       int 
       
       mapMax,
       
       mapMin;
       
       int 
       
       dir[
       
       4][
       
       2]
       
       ={
       
       1,
       
       0,
       
       -
       
       1,
       
       0,
       
       0,
       
       1,
       
       0,
       
       -
       
       1};
       
       bool 
       
       vis[
       
       105][
       
       105];
       
       int 
       
       n;
       
       bool 
       
       limit(
       
       int 
       
       x,
       
       int 
       
       y)
       
{
       
       if(
       
       x
       
       <
       
       0
       
       ||
       
       y
       
       <
       
       0
       
       ||
       
       x
       
       >=
       
       n
       
       ||
       
       y
       
       >=
       
       n
       
       ||
       
       vis[
       
       x][
       
       y]) 
       
       return 
       
       false;
       
       return 
       
       true;
       
}
       
       bool 
       
       dfs(
       
       int 
       
       l,
       
       int 
       
       r,
       
       int 
       
       x,
       
       int 
       
       y)
       
{
       
       vis[
       
       x][
       
       y]
       
       =
       
       true;
       
       if(
       
       x
       
       ==
       
       n
       
       -
       
       1
       
       &&
       
       y
       
       ==
       
       n
       
       -
       
       1)
       
  {
       
       return 
       
       true;
       
  }
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       4;
       
       i
       
       ++)
       
  {
       
       int 
       
       xx
       
       =
       
       dir[
       
       i][
       
       0]
       
       +
       
       x;
       
       int 
       
       yy
       
       =
       
       dir[
       
       i][
       
       1]
       
       +
       
       y;
       
       if(
       
       limit(
       
       xx,
       
       yy)
       
       &&
       
       map[
       
       xx][
       
       yy]
       
       >=
       
       l
       
       &&
       
       map[
       
       xx][
       
       yy]
       
       <=
       
       r)
       
    {
       
       if(
       
       dfs(
       
       l,
       
       r,
       
       xx,
       
       yy))
       
       return 
       
       true;
       
    }
       
  }
       
       return 
       
       false;
       
}
       
       bool 
       
       can(
       
       int 
       
       x)
       
{
       
       //遍历可能的难度差 
       
       for(
       
       int 
       
       i
       
       =
       
       mapMin;
       
       i
       
       <=
       
       mapMax;
       
       i
       
       ++)
       
  {
       
       if(
       
       i
       
       +
       
       x
       
       >
       
       mapMax) 
       
       break;
       
       if(
       
       map[
       
       0][
       
       0]
       
       <
       
       i
       
       ||
       
       map[
       
       0][
       
       0]
       
       >
       
       i
       
       +
       
       x) 
       
       continue;
       
       memset(
       
       vis,
       
       false,
       
       sizeof(
       
       vis));
       
       if(
       
       dfs(
       
       i,
       
       i
       
       +
       
       x,
       
       0,
       
       0))
       
       return 
       
       true; 
       
  }
       
       return 
       
       false;
       
}
       
       //二分法查找可能的最小结果 
       
       int 
       
       find()
       
{
       
       int 
       
       l
       
       =
       
       0,
       
       r
       
       =
       
       mapMax
       
       -
       
       mapMin
       
       +
       
       1,
       
       mid;
       
       while(
       
       l
       
       <
       
       r)
       
  {
       
       mid
       
       =(
       
       l
       
       +
       
       r)
       
       /
       
       2;
       
       //如果地图中有当前结果 缩小结果范围 
       
       if(
       
       can(
       
       mid))
       
    {  
       
       r
       
       =
       
       mid;
       
    }
       
       else
       
    {
       
       l
       
       =
       
       mid
       
       +
       
       1;
       
    }
       
  }
       
       return 
       
       r;
       
}
       
       int 
       
       main()
       
{
       
       while(
       
       ~scanf(
       
       "%d",
       
       &
       
       n))
       
  {
       
       mapMax
       
       =-
       
       INF;
       
       mapMin
       
       =
       
       INF;
       
       memset(
       
       map,
       
       0,
       
       sizeof(
       
       map));
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       n;
       
       i
       
       ++)
       
    {
       
       for(
       
       int 
       
       j
       
       =
       
       0;
       
       j
       
       <
       
       n;
       
       j
       
       ++)
       
      {
       
       scanf(
       
       "%d",
       
       &
       
       map[
       
       i][
       
       j]);
       
       mapMax
       
       =
       
       max(
       
       mapMax,
       
       map[
       
       i][
       
       j]);
       
       mapMin
       
       =
       
       min(
       
       mapMin,
       
       map[
       
       i][
       
       j]);
       
      }
       
    }
       
       printf(
       
       "%d\n",
       
       find());
       
  }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15742657/5557835

当前位置：网站首页>nyoj306 走迷宫(搜索+二分)

nyoj306 走迷宫(搜索+二分)

走迷宫

边栏推荐

猜你喜欢

随机推荐