老鼠走迷宫

深碍√TFBOYSˉ_ 2022-12-24 05:48 99阅读 0赞

## 老鼠走迷宫 ##

Description  
现在一只老鼠被困在了迷宫里！你需要判断老鼠能否走出迷宫。

老鼠只能向上下左右四个方向移动。我们认为只要老鼠走到了迷宫的边界即算走出迷宫。

Input  
第一行输入两个整数 nn, mm (1 \\leqslant n, m \\leqslant 100)(1⩽n,m⩽100) 表示迷宫地图的尺寸。

接下来输入 nn 行，每行 mm 个字符，表示迷宫地图。其中 M 表示老鼠的位置，\* 代表墙壁，. 代表空地。

Output  
如果老鼠可以走出迷宫，则输出一行 Yes，否则输出一行 No。

Sample  
Input  
![在这里插入图片描述][20201126215909433.png_pic_center]

Output  
Yes

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int map[1100][1100], vis[1100][1100];//在二位坐标系下，map记录该点是否可走，vis标记该点是否访问
    int flag, n, m;
    //dx，dy表示四个方向：上、下、右、左
    int dx[] = {
        0,0,1,-1};
    int dy[] = {
        1,-1,0,0};
    void DFS(int x, int y)
    {
        
    	vis[x][y] = 1;
    	if (x == 0 || y == 0 || x == n - 1 || y == m - 1)//如果老鼠已经到达迷宫边界
    	{
        
    		flag = 1;
    		return;
    	}
    	for (int i = 0; i < 4; i++)//老鼠未到达迷宫边界，则从该点的四个方向继续访问
    	{
        
    		int xx = x + dx[i];
    		int yy = y + dy[i];
    		if (map[xx][yy] == 1 && vis[xx][yy] == 0 && xx >= 0 && xx < n && yy >= 0 && yy < m)//该点的四个方向点未被访问且可走并且不是迷宫边界点，
    			DFS(xx, yy);
    	}
    }
    int main()
    {
        
    	char s;
    	int kx, ky;
    	scanf("%d %d", &n, &m);
    	memset(map, 0, sizeof(map));
    	memset(vis, 0, sizeof(vis));
    	for (int i = 0; i < n; i++)//构建地图
    	{
        
    		getchar();
    		for (int j = 0; j < m; j++)
    		{
        
    			scanf("%c", &s);
    			if (s == '*')
    				map[i][j] = 0;
    			else if (s == '.')
    				map[i][j] = 1;
    			else
    			{
        
    				map[i][j] = 1;
    				kx = i;
    				ky = j;
    			}
    		}
    	}
    	flag = 0;
    	DFS(kx, ky);
    	if (flag)
    		printf("Yes\n");
    	else
    		printf("No\n");
    }

[20201126215909433.png_pic_center]: /images/20221120/e889c7829bfa4d1eb09afa0f4b6a55dc.png