迷宫问题（0可走，打印路径）POJ3984

妖狐艹你老母 2022-05-25 02:15 187阅读 0赞

BFS AC代码

//AC
    #include <iostream>
    #include <cstdio>
    #include <queue>
    using namespace std;
    int Map[5][5];
    int step[5][5];
    int visit[5][5];
    int dx[]={1,0,-1,0};
    int dy[]={0,1,0,-1};
    
    struct node{
    	int x,y;
    };
    queue<node>Q;
    void show_route(int x,int y)
    {
    	if(x==0 && y==0){
    		printf("(%d, %d)\n",x,y);
    		return;
    	}
    	for(int i=0;i<4;i++){   //按照值递减，打印路径
    		int x2=x+dx[i];
    		int y2=y+dy[i];
    		if( (step[x][y] - step[x2][y2]==1) && Map[x2][y2]==0 && x2>=0 && x2<=4 && y2>=0 && y2<=4 ){
    			show_route(x2,y2);
    		}
    	}
    	printf("(%d, %d)\n",x,y);   //只能放在这个位置
    }
    void BFS()
    {
    	node n1;
    	n1.x=0;n1.y=0;
    	Q.push(n1);visit[0][0]=1;step[0][0]=1;
    	
    	while(!Q.empty()){
    		node Now=Q.front(); Q.pop();
    		if(Now.x==4 && Now.y==4){
    			Q.push(Now);
    			show_route(4,4);
    			break;
    		}
    		node Next;
    		for(int i=0;i<4;i++){
    			Next.x=Now.x + dx[i];
    			Next.y=Now.y + dy[i];
    			if(Map[Next.x][Next.y]==0&&Next.x>=0&&Next.x<=4&&Next.y>=0&&Next.y<=4 && !visit[Next.x][Next.y] ){
    				Q.push(Next);   //新的点，入栈
    				step[Next.x][Next.y] = step[Now.x][Now.y]+1;//路径长度加一
    				visit[Next.x][Next.y]=1;//标记改点走过
    			}
    		}
    	}
    }
    int main()
    {
    	for(int i=0;i<5;i++){
    		for(int j=0;j<5;j++)
    			scanf("%d",&Map[i][j]);
    	}
    	BFS();
    	return 0;
    }

DFS AC代码

//AC
    #include <stdio.h>
    #include <string.h>
    
    const int maxn = 6;
    int Map[maxn][maxn];
    int visit[maxn][maxn];
       //下，右，上，左
    const int dir[4][2]= {
       {1,0},{0,1},{-1,0},{0,-1}};
    struct node {
        int x;
        int y;
    };
    
    node route[25];     // 1表示墙壁，0 表示可以走
    int Cnt=0;
    int num=0;
    int biao=0;
    
    void DFS(int x,int y)
    {
    	if(x==4 && y==4){   //最后一个 dfs 和 第一个 dfs ，只会执行这一个函数
    		biao=1;
    	  	route[num].x = x;
    		route[num++].y = y;
    		return ;
    	}
    	int i;
    	int tx,ty;
    	for(i=0;i<4;i++){
    		tx = x+dir[i][0];
    		ty = y+dir[i][1];
    		if(visit[tx][ty]==1 || tx <0 || tx >=5 || ty <0 || ty >= 5)//如果越界
    			continue;
            if(Map[tx][ty]==1) continue;//如果不能走
    		visit[tx][ty]=1;//标记已经走过
    		
    		DFS(tx,ty);
    		
    		if(biao)
    		{
    			route[num].x = x;
    			route[num++].y = y;
    			return ;
    		}
    		visit[tx][ty]=0;
    	}
    }
    
    int main()
    {
    	memset(visit,0,sizeof(visit));
    	for(int i=0;i<5;i++)
    		for(int j=0;j<5;j++)
    			scanf("%d",&Map[i][j]);
    	num=1;
    	visit[0][0]=1;
    	DFS(0,0);
    	for(int i = num-1 ; i >=1 ; i --)
    		printf("(%d, %d)\n",route[i].x, route[i].y);
    	return 0;
    }