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

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;
    }
    

     

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 数据库数据成问号了,前台查询正常,数据库查询是?号
  • ¥15 算法使用了tf-idf,用手肘图确定k值确定不了,第四轮廓系数又太小才有0.006088746097507285,如何解决?(相关搜索:数据处理)
  • ¥15 彩灯控制电路,会的加我QQ1482956179
  • ¥200 相机拍直接转存到电脑上 立拍立穿无线局域网传
  • ¥15 (关键词-电路设计)
  • ¥15 如何解决MIPS计算是否溢出
  • ¥15 vue中我代理了iframe,iframe却走的是路由,没有显示该显示的网站,这个该如何处理
  • ¥15 操作系统相关算法中while();的含义
  • ¥15 CNVcaller安装后无法找到文件
  • ¥15 visual studio2022中文乱码无法解决