「已注销」
2020-12-05 15:53
采纳率: 100%
浏览 277

c语言二维数组迷宫问题(加急!)

迷宫问题。编程找出从入口(左上角方格)经过迷宫到达出口(右下角方格)的所有路径,迷宫问题示意如下方数字阵列所示,0所表示的地方是不可以通行的,只能从1走到与它相邻(四邻域:上、下、左、右相邻)的1上,且不能走重复路径。

输出三个结果

测试输入给出为:6 10 1 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • 小黑哎呀 2020-12-05 18:47
    已采纳
    #include<stdio.h>
    #include<string.h>
    #define N 1001
    struct st{
    	int x;
    	int y;
    }s[N];//记录路径坐标的栈 
    int Map[N][N];//地图
    int step[N][N];//路径地图 
    int flag[N][N];//标记地图 
    int next[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//方向 上,右,左,下 
    int n,m,k=1,num=1;
    void input()
    {
    	s[0].x=s[0].y=1;
    	for(int i=0;i<k;i++)
    	{
    		int x=s[i].x;
    		int y=s[i].y;
    		step[x][y]=1;//标记路径 
    		//printf("(%d,%d) ",x,y);
    	}
    	printf("%d\n",num++);//输出路径编号 
    	for(int i=1;i<=n;i++)//输出地图路径 
    	{
    		for(int j=1;j<=m;j++)
    		{
    			printf("%d",step[i][j]);
    			if(j!=m)
    			printf(" ");
    		}
    		printf("\n");
    	}
    	memset(step,0,sizeof(step));//路径地图置0,防止干扰下次输出 
    }
    void dsf(int x,int y)
    {
    	if(x==n&&y==m)
    	{//到达终点,输出 
    		input(); 
    		return;
    	}
    	int nx,ny;
    	for(int i=0;i<4;i++)
    	{
    		nx=x+next[i][0];
    		ny=y+next[i][1];
    		if(nx<=n&&ny<=m)//判断是否越界,是否可通过 
    		if(flag[nx][ny]==0&&Map[nx][ny]==1)
    		{
    			flag[nx][ny]=1;
    			s[k].x=nx;// 记录路径上的坐标 (入栈)
    			s[k++].y=ny;//记录路径上的坐标 (入栈) 
    			dsf(nx,ny);//前往下一个点 
    			flag[nx][ny]=0;//回溯(走过的路,退回) 
    			k--;//(出栈)
    		}
    	}	
    }
    /*
    4 5 
    1 0 0 0 0
    1 1 1 1 1
    1 0 1 0 1
    1 1 1 1 1
    */
    int main() 
    {
    	memset(Map,0,sizeof(Map));//置0 
    	memset(flag,0,sizeof(flag));
    	scanf("%d%d",&n,&m);//行 列 
    	for(int i=1;i<=n;i++)//地图 
    	{
    		for(int j=1;j<=m;j++)
    		{
    			scanf("%d",&Map[i][j]);
    		}
    	}
    	dsf(1,1);//从左上角开始,向右下角走 
    	return 0;
    }
    

     

    已采纳该答案
    评论
    解决 2 无用 1
    打赏 举报
  • Corleo 2020-12-05 16:37

    直接用BFS就行,然后用一个二维数组来记录每个节点是从哪些节点过来的,打印答案就是从终点往前打印

    评论
    解决 3 无用
    打赏 举报

相关推荐 更多相似问题