poj 3984 迷宫问题【dfs】

￡神魔★判官ぃ 2022-08-09 01:48 133阅读 0赞

迷宫问题

Sample Input

0 1 0 0 0
    0 1 0 1 0
    0 0 0 0 0
    0 1 1 1 0
    0 0 0 1 0

Sample Output

(0, 0)
    (1, 0)
    (2, 0)
    (2, 1)
    (2, 2)
    (2, 3)
    (2, 4)
    (3, 4)
    (4, 4)

思路：遍历从（0,0）到（4,4）的走法，每走一步，就要更新到当前格子所需的最少的步数【为之后的输出做铺垫，笔者使用与map一样的的数组来存放  到对应的格子所需的最小步数】；完成遍历后，

①从（4,4）开始往回走，设到（4,4）最小步数为n，则（4,4）之前的格子所需最少步数为n-1，然后查找与（4，4）相邻的格子，查看他们所需的步数，找出n-1步的，

②然后从n-1不的那个格子开始，找出与它相邻的n-2的格子，

③重复上述操作即可。。。

已Accept【c++提交】

#include <cstdio>
    #include <cstring>
    //#include <cstdlib>
    using namespace std;
    int map[6][6];
    int dis[7][7];
    int n[18];
    int m[18];
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    
    void dfs(int sc, int sr, int total) {
    	if(sc < 1 || sc > 5 || sr < 1 || sr > 5)		//判断是否越界 
    		return ;
    	if(map[sc][sr] == 1)							//判断是否是墙 
    		return ;
    	if(total  + 1 >= dis[sc][sr])					//若当前走到得格子原先到过且所需最小步数比现在 少，则不更新 ，反之则更新 
    		return ;
    	dis[sc][sr] = total  + 1 ;
    	map[sc][sr] = 1;
    	for(int i = 0; i < 4; i++) {					//当前格子的相邻的四个格子遍历过去 
    		int nx = sc + dx[i];
    		int ny = sr + dy[i];
    		dfs(nx, ny, dis[sc][sr]);
    	}
    	map[sc][sr] = 0;
    	return ;
    }
    
    void Scanf_a() {									//输入 
    	memset(dis, 0x3f, sizeof(dis));
    	for(int i = 1; i < 6; i++)
    		for(int j = 1; j < 6; j++)
    			scanf("%d", &map[i][j]);
    }
    
    void Printf_a() {									//输出 
    	int x = 5, y = 5, q = 0;
    	int current = dis[x][y];
    	n[q] = x;
    	m[q++] = y;
    	while(x != 1 || y !=1) {
    		for(int i = 0; i < 4; i++) {
    			if(dis[x + dx[i]][y + dy[i]] == current - 1) {
    				x = x + dx[i];
    				y = y + dy[i];
    				n[q] = x;
    				m[q++] = y;
    				current--;
    			}
    		}
    	}
    	for(int j = dis[5][5] - 1; j >= 0; j--)
    		printf("(%d, %d)\n", n[j] - 1, m[j] - 1);
    }
    
    int main(){
    	Scanf_a();
    	dfs(1, 1, 0);
    	Printf_a();
    	//system("pause");
    	return 0;
    }