Happy Birthday！LevOJ P1793 求解迷宫问题

思路：

BFS或者DFS都可以做。

之前会把DFS卡到一种很坏的情况，现在修改样例可以AC了。

BFS要记录一下路径。

AC代码(DFS)：

#include<bits/stdc++.h>

using namespace std;

char maze[8][8];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};


void dfs(int a,int b){
    if(a==7&&b==7){
        maze[7][7]=' ';
        for(int i=0;i<=7;i++){
            for(int j=0;j<=7;j++){
                    printf("%c",maze[i][j]);
            }
            cout<<endl;
        }
    }else{
        for(int i=0;i<4;i++){
            int nx=a+dx[i];
            int ny=b+dy[i];
            if(nx>=0&&nx<=7&&ny>=0&&ny<=7&&maze[nx][ny]=='O'){
                maze[nx][ny]=' ';
                dfs(nx,ny);
                maze[nx][ny]='O';
            }
        }
    }
}
int main(){
    for(int i=0;i<=7;i++){
        for(int j=0;j<=7;j++){
            scanf("%c",&maze[i][j]);
        }
        getchar();
    }
    dfs(0,0);
    return 0;
}

AC代码(BFS)：

#include<bits/stdc++.h>

using namespace std;


char maze[8][8];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};

int front=-1,rear=-1;

struct point
{
    int x;
    int y;
    int pre;
};

point q[100];

void output(int front){
    for(int i=0;i<=7;i++){
        for(int j=0;j<=7;j++){
            if(maze[i][j]=='*'){
                maze[i][j]='O';
            }
        }
    }
    int k=front;
    while(k!=-1){
        maze[q[k].x][q[k].y]=' ';
        k=q[k].pre;
    }
    for(int i=0;i<=7;i++){
        for(int j=0;j<=7;j++){
            cout<<maze[i][j];
        }
        cout<<endl;
    }
}

void bfs()
{
    point start,now,next;
    start.x=0;
    start.y=0;
    start.pre=-1;
    maze[start.x][start.y]='*';
    rear++;
    q[rear]=start;
    while(front!=rear){
        front++;
        now=q[front];
        if(now.x==7&&now.y==7){
            output(front);
            return;
        }
        for(int i=0;i<4;i++){
            next.x=now.x+dx[i];
            next.y=now.y+dy[i];
            if(next.x>=0 && next.x<=7 && next.y>=0 && next.y<=7 && maze[next.x][next.y]=='O')
            {
                maze[next.x][next.y]='*';
                next.pre=front;
                rear++;
                q[rear]=next;
            }
        }
    }
    return;
}
int main(){
    for(int i=0;i<=7;i++){
        for(int j=0;j<=7;j++){
            scanf("%c",&maze[i][j]);
        }
        getchar();
    }
    bfs();
    return 0;
}