走迷宫（bfs）

后补...

#include<cstdio>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<queue>
int mp[6][6];
int n=5;
int d[4][2]={-1,0,0,1,1,0,0,-1};
using namespace std;
int head=0,tail=1;
struct node{
    int x,y,step;
}way[105];
void fun(int i){
    if(way[i].step!=-1){
        fun(way[i].step);
        printf("(%d,%d)\n",way[i].x,way[i].y);
    }
    else
        printf("(%d,%d)\n",way[i].x,way[i].y);
}
void bfs(int x,int y){
    way[head].x=x;
    way[head].y=y;
    way[head].step=-1;
    while(head<tail){
        for(int i=0;i<4;i++){
            x=way[head].x+d[i][0];
            y=way[head].y+d[i][1];
            if(x<0||x>=n||y<0||y>=n||mp[x][y]==1){
                continue;
            }
            else {
                mp[x][y]=1;
                way[tail].x=x;
                way[tail].y=y;
                way[tail].step=head;
                tail++;
            }
            if(x==4&&y==4)
                fun(head);
        }
        head++;
    }
}
int main(){
    memset(mp,0,sizeof(mp));
    //freopen("e:/a.in","r",stdin);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&mp[i][j]);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%d ",mp[i][j]);
        }
        printf("\n");
    }
   bfs(0,0);
    printf("(4,4)\n");
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int MAXN = 100+10;
int q[MAXN*MAXN];
//走迷宫
int vis[MAXN][MAXN];
int fa[MAXN][MAXN];
int dist[MAXN][MAXN];
int maze[MAXN][MAXN]; 
int last_dir[MAXN][MAXN]; 
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0}; 
int n,m;//m表示一行有多少元素 
char name[4]={'R','L','D','U'}; 
void bfs(int x,int y){
    
    //初始化 
    int front=0,rear=0,d,u;
    u=x*m+y;      
    vis[x][y] = 1;  //标记已经访问过。
    fa[x][y] = u;   //起点的根节点设置为u，循环输出路径的结束条件
    dist[x][y] = 0; //路径长度初始为0.
    q[rear++] = u;  //起点入队列。
    while(front < rear){
        u=q[front++];
        //得到当前节点。 
        x=u/m; y=u%m;
        for(d = 0; d < 4; d++){//分别往四个方向走 
            int nx=x+dx[d],ny=y+dy[d];
            if(nx>=0 && nx<n && ny>=0 && ny<m 
                && maze[nx][ny] && !vis[nx][ny]){//maze表示如果单元格是空地
                int v=nx*m+ny;
                q[rear++]=v;
                vis[nx][ny]=1;
                fa[nx][ny]=u;  //静态链表记录祖先结点，右边是祖先。
                dist[nx][ny] = dist[x][y] + 1;//到nx,ny的距离等于到x,y的距离加1.
                last_dir[nx][ny] = d;//保存从父节点移动到此的方向。 
            }
        }    
    }       
} 
 
/
//打印路径,递归形式 
void print_path(int x,int y){
    int fx = fa[x][y]/m;
    int fy = fa[x][y]%m;
    if(fx!=x || fy!=y){
        print_path(fx,fy);
        putchar(name[last_dir[x][y]]);
    }
} 
 
//打印路径，非递归形式
int dir[MAXN*MAXN];
void print_path2(int x,int y){
    int c=0;
    for(;;){
        int fx=fa[x][y]/m;
        int fy=fa[x][y]%m;
        if(fx==x && fy==y)
            break;
        dir[c++]=last_dir[x][y];
        x=fx;
        y=fy;
    }
    while(c--){
        putchar(name[dir[c]]);
    }
} 
int main() {
    freopen("d:/bfs.in","r",stdin);
    //输入几行几列
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            maze[i][j]=1;
        }
    }/打印
memset(vis,0,sizeof(vis));
    memset(fa,0,sizeof(fa));
    memset(dist,0,sizeof(dist));    
    memset(last_dir,0,sizeof(last_dir));
 
    int total,xx,yy;
    scanf("%d",&total); 

    for(int j=0;j<total;j++){//将墙壁初始化为0
        scanf("%d %d",&xx,&yy);
        maze[xx][yy]=0;
    }
    bfs(0,1);
    print_path2(3,4);
    return 0;
 }