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

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条)

报告相同问题?

悬赏问题

  • ¥20 matlab可以把多个二维图合成为三维瀑布图吗
  • ¥15 EEPROM,软件i2c
  • ¥500 求解读该段JS代码,需要知道是用干什么的
  • ¥20 qt4代码实现二进制文件读取显示,以及显示的内容进行搜索
  • ¥15 Labview获取LK-G3001数据
  • ¥15 我知道什么是混合树,但是怎么写代码啊
  • ¥50 开发板linux系统安装dpkg,apt函数库 有偿
  • ¥15 浏览器时间循环 交互事件和延时事件的 优先级与执行问题
  • ¥15 GD模块安装出错,libgd无法正常安装
  • ¥20 求有缘人帮我把笛卡尔坐标系转换为经纬度 有偿