迷宫

#include <stdio.h>
//看来还是得用BFS啊，深度没那么大
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//看来你的思路对了，只需要把dfs改成bfs就行了
int n, m;
int S_x, S_y, E_x, E_y;
int E_min_x, E_max_x, E_min_y, E_max_y;
bool E_to_S = false;
bool S_to_E = false;  // 添加这个全局标志
// 使用BFS替代DFS
void bfs(char** migong, int start_x, int start_y, bool is_E_to_S) {
    // 简单的队列实现
    int* queue_x = malloc(n * m * sizeof(int));
    int* queue_y = malloc(n * m * sizeof(int));
    int front = 0, rear = 0;
    
    // 入队起点
    queue_x[rear] = start_x;
    queue_y[rear] = start_y;
    rear++;
    migong[start_x][start_y] = '#';
    
    while (front < rear) {
        int x = queue_x[front];
        int y = queue_y[front];
        front++;
        
        if (is_E_to_S) {
            // E到S的BFS
            if (x == S_x && y == S_y) {
                printf("YES\n");
                E_to_S = true;
                free(queue_x);
                free(queue_y);
                return;
            }
            
            // 更新E连通块边界
            if (x-1 < E_min_x && x-1 >= 0) E_min_x = x-1;
            if (x+1 > E_max_x && x+1 < n) E_max_x = x+1;
            if (y-1 < E_min_y && y-1 >= 0) E_min_y = y-1;
            if (y+1 > E_max_y && y+1 < m) E_max_y = y+1;
        } else {
            // S到E范围的检查
            if ((x >= E_min_x && x <= E_max_x) || (y >= E_min_y && y <= E_max_y)) {
                printf("YES\n");
                S_to_E = true;  // 设置标志
                free(queue_x);
                free(queue_y);
                return;
            }
        }
        
        // 四个方向
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (is_E_to_S) {
                    if (migong[nx][ny] == '.' || migong[nx][ny] == 'S') {
                        migong[nx][ny] = '#';
                        queue_x[rear] = nx;
                        queue_y[rear] = ny;
                        rear++;
                    }
                } else {
                    if (migong[nx][ny] == '.' || migong[nx][ny] == 'E') {
                        migong[nx][ny] = '#';
                        queue_x[rear] = nx;
                        queue_y[rear] = ny;
                        rear++;
                    }
                }
            }
        }
    }
    
    free(queue_x);
    free(queue_y);
}

int main() {
    scanf("%d %d", &n, &m);
    char** migong = malloc(sizeof(char*) * n);
    char** migong_copy = malloc(sizeof(char*) * n); // 备份迷宫
    
    for (int i = 0; i < n; i++) {
        migong[i] = malloc(sizeof(char) * (m + 1));
        migong_copy[i] = malloc(sizeof(char) * (m + 1));
        scanf("%s", migong[i]);
        // 备份迷宫
        for (int j = 0; j < m; j++) {
            migong_copy[i][j] = migong[i][j];
        }
        migong_copy[i][m] = '\0';
    }
    
    // 获取S和E的坐标
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (migong[i][j] == 'S') {
                S_x = i;
                S_y = j;
            }
            if (migong[i][j] == 'E') {
                E_x = i;
                E_y = j;
                // 初始化E连通块边界
                E_min_x = E_x - 1 >= 0 ? E_x - 1 : 0;
                E_max_x = E_x + 1 < n ? E_x + 1 : E_x;
                E_min_y = E_y - 1 >= 0 ? E_y - 1 : 0;
                E_max_y = E_y + 1 < m ? E_y + 1 : E_y;
            }
        }
    }
    
    migong[E_x][E_y] = '.';
    bfs(migong, E_x, E_y, true); // E到S的BFS
    
    if (!E_to_S) {
        // 恢复迷宫状态
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                migong_copy[i][j] = migong_copy[i][j]; // 使用备份
            }
        }
        bfs(migong_copy, S_x, S_y, false); // S到E范围的BFS
        if (!S_to_E) {
            printf("NO\n");
        }
    }
    
    // 释放内存
    for (int i = 0; i < n; i++) {
        free(migong[i]);
        free(migong_copy[i]);
    }
    free(migong);
    free(migong_copy);
    
    return 0;
}