解题思路

1. 预处理迷宫

• 初始化迷宫：
  • 将整个字符数组（char 类型）初始化为 '.'（地板）。
  • 实际迷宫数据存储在 1 到 n 行和 1 到 m 列，避免边界问题。

2. 起点搜索

• 从虚拟起点 (0, 0) 开始搜索：
  • 由于迷宫数据存储在 1 到 n 行和 1 到 m 列，(0, 0) 是一个虚拟点，不属于迷宫内部。
  • 从 (0, 0) 出发，可以方便地找到迷宫的入口（即第一个 '.' 的相邻点）。

3. 左转优先搜索

• 方向定义：

  • 使用 $4$ 个方向（上、右、下、左），按 左转优先 顺序遍历。
  • 例如：当前方向为 右，则优先尝试 上（左转），再 右（直行），最后 下（右转）。

• 搜索过程：

  • 从入口进入，按照 始终左转 的规则移动。
  • 如果无法左转，则尝试直行；若仍无法移动，则右转或后退。

4. 判断是否到达中心

• 终止条件：
  • 如果按照左转规则能走到 中心庭院（即某个 '.' 被判定为中心点），则迷宫是 左转迷宫（输出 YES）。
  • 如果遍历所有可能路径仍未到达中心，则迷宫 不是左转迷宫（输出 NO）。

关键优化

• 边界处理：

  • 由于迷宫数据存储在 1 到 n 行和 1 到 m 列，(0, 0) 作为虚拟起点，可以避免复杂的边界判断。

• 方向管理：

  • 使用 方向数组 存储 $4$ 个移动方向（如 int dir[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}}）。
  • 每次优先尝试 左转方向，确保符合题目要求。

复杂度分析

• 时间复杂度：
  • 最坏情况下，需要遍历整个迷宫，复杂度为 $O(n \times m)$。
• 空间复杂度：
  • 使用二维数组存储迷宫，空间复杂度为 $O(n \times m)$。

# include <iostream>
# include <cstring>
# include <stdio.h>
using namespace std;
char mg[120][120];
int n,m;
int tx,ty,sx,sy;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
bool dir[120][120][4];
bool vis[120][120];
bool ans;
struct point{
    int x,y;
};
point pp[10000];
bool isok(int x,int y){
    if(x>=0&&x<=n+1&&y>=0&&y<=m+1) return true;
    else return false;
}
bool isok2(int x,int y){
    if(x>=1&&x<=n&&y>=1&&y<=m) return true;
    else return false;
}
bool istrue(int x,int y){
    if(isok2(x+1,y+1)&&mg[x+1][y]=='.'&&mg[x+1][y+1]=='.'&&mg[x][y+1]=='.') return true;
    if(isok2(x-1,y-1)&&mg[x-1][y]=='.'&&mg[x-1][y-1]=='.'&&mg[x][y-1]=='.') return true;
    if(isok2(x-1,y+1)&&mg[x-1][y]=='.'&&mg[x-1][y+1]=='.'&&mg[x][y+1]=='.') return true;
    if(isok2(x+1,y-1)&&mg[x][y-1]=='.'&&mg[x+1][y-1]=='.'&&mg[x+1][y]=='.') return true;
    return false;
}
void bfs(){
    int front = 0,rear = 0;
    point st;
    st.x = 0,st.y = 0;
    vis[0][0] = true;
    mg[st.x][st.y] = '*';
    pp[rear++] = st;
    point tp;
    while(front<rear){
        tp = pp[front++];
        if((mg[tp.x-1][tp.y]=='#'&&mg[tp.x+1][tp.y]=='#')||(mg[tp.x][tp.y-1]=='#'&&mg[tp.x][tp.y+1]=='#')){
            sx = tp.x;sy = tp.y;
            return ;
        }
        mg[tp.x][tp.y] = '*';
        for(int i=0;i<4;++i){
            int xx = tp.x+dx[i];
            int yy = tp.y+dy[i];
            if(isok(xx,yy)){
                if(!vis[xx][yy]&&mg[xx][yy] == '.'){
                    point temp;
                    temp.x = xx;temp.y = yy;
                    vis[xx][yy] = true;
                    pp[rear++] = temp;
                }
            }
        }
    }
}
void dfs(int x,int y,int d){
    //printf("%d            %d\n",x,y);
    if(ans == true) return ;
    //dir[x][y][d] = true;
    if(istrue(x,y)){
        ans = true;
    }
    else{
        //printf("11111\n");
        for(int i=3;i<=6;++i){
            int td = (d+i)%4;
            //printf("%d\n",td);
            if(isok2(x+dx[td],y+dy[td])&&dir[x][y][td] == false&&mg[x+dx[td]][y+dy[td]]=='.'){
                dir[x][y][td] = true;
                dfs(x+dx[td],y+dy[td],td);
                break;
            }
        }
    }
}
int main()
{
    //freopen("1.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(vis,false,sizeof(vis));
        memset(mg,'.',sizeof(mg));
        //sx = 1,sy = 1;
        getchar();
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                scanf("%c",&mg[i][j]);
            }
            getchar();
        }
        bfs();
        //printf("%d     %d\n",sx,sy);
        for(int i=0;i<=n;++i){
            for(int j=0;j<=m;++j){
                if(mg[i][j] == '*') mg[i][j] = '#';
            }
        }
        /*for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                printf("%c",mg[i][j]);
            }
            printf("\n");
        }*/
        memset(dir,false,sizeof(dir));
        ans = false;
        dfs(sx,sy,0);
        if(ans) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}