thank

深度搜索的思路

一个简单小例子:

给定一个起点，终点，以及中途的道路和墙壁

求问，能不能从起点到终点？

s代表起点，g代表终点，.代表道路，＃代表墙壁

输入n，ｍ　表示有n行m列

如:

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#.....#...

思路

//x,y代表起点的坐标
int n, m, x, y;
//输入的地图
char[][] arr;
//判断哪些坐标已经走过
boolean[][] flag;
//用来向右左上下方向前进
int[][] dir = { {0,1},{0,-1},{1,0},{-1,0} };

/**
判断坐标是否在地图中
*/
static boolean in(int x, int y){
    return 0 <= x && x < n && 0 <= y && y <=m;
}

//深度搜索算法,由于起点必定在地图里,所以开始并不需要判断
static boolean dfs(int x, int y){
    if(arr[x][y] == 'g') return true;	//到达终点
    flag[x][y] = true;					//标记
    //很巧妙的方法,看别人写的
    for(int i = 0; i < 4; i++){
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if(in(tx, ty) && arr[tx][ty] != '#' && !flag[tx][ty]){
            //如果这个点是终点,就直接返回
            if(dfs(tx, ty)) return true;
        }
    }
    return false;
}

到此,简单的深度搜索就完成了(就是暴力)

如果要搜索最短路径, 只需该亿点点代码就ok了

int now = 0, min = 0x3f3f3f3f;		//now表示当前路径长度,min表示最短的

//算上起点的距离,不算终点的距离
static void dfs(int x, int y){
    if(arr[x][y] == 'g'){
        min = now < min ? now : min;	//将最小值赋予min
        return;
    }
    flag[x][y] = true;					//标记
    now++;	
    //很巧妙的方法,看别人写的
    for(int i = 0; i < 4; i++){
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if(in(tx, ty) && arr[tx][ty] != '#' && !flag[tx][ty]){
			dfs(tx,ty);		   			//把所有点都逛一遍
        }
    }
    now--;								//返回
    flag[x][y] = false;					//回溯
}

这样就写好了!😉