代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_M 12
 
struct node {
    int x, y;
    int tcnt;
};
 
int m, t;
char mat[MAX_M][MAX_M];
 
int bfs(int x0, int y0, int x1, int y1) {
    if (x0 == x1 && y0 == y1) {
        return 0;
    }
    struct node nd = {x0, y0, 0};
    int x, y;
    struct node q[MAX_M * MAX_M];
    int front = 0, rear = 0;
    q[rear++] = nd;
    while (front < rear) {
        nd = q[front++];
        x = nd.x;
        y = nd.y;
        if (x < m - 1) {
            if (mat[x + 1][y] == 'E') {
                return nd.tcnt + 1;
            } else if (mat[x + 1][y] == '.') {
                struct node newNode = {x + 1, y, nd.tcnt + 1};
                q[rear++] = newNode;
                mat[x + 1][y] = '*';
            }
        }
        if (x > 0) {
            if (mat[x - 1][y] == 'E') {
                return nd.tcnt + 1;
            } else if (mat[x - 1][y] == '.') {
                struct node newNode = {x - 1, y, nd.tcnt + 1};
                q[rear++] = newNode;
                mat[x - 1][y] = '*';
            }
        }
        if (y < m - 1) {
            if (mat[x][y + 1] == 'E') {
                return nd.tcnt + 1;
            } else if (mat[x][y + 1] == '.') {
                struct node newNode = {x, y + 1, nd.tcnt + 1};
                q[rear++] = newNode;
                mat[x][y + 1] = '*';
            }
        }
        if (y > 0) {
            if (mat[x][y - 1] == 'E') {
                return nd.tcnt + 1;
            } else if (mat[x][y - 1] == '.') {
                struct node newNode = {x, y - 1, nd.tcnt + 1};
                q[rear++] = newNode;
                mat[x][y - 1] = '*';
            }
        }
    }
    return -1;
}
 
int main() {
    int k, i, j, x0, y0, x1, y1, ans;
    scanf("%d", &k);
    while (k--) {
        scanf("%d %d", &m, &t);
        for (i = 0; i < m; i++) {
            for (j = 0; j < m; j++) {
                scanf(" %c", &mat[i][j]);
                if (mat[i][j] == 'S') {
                    x0 = i;
                    y0 = j;
                } else if (mat[i][j] == 'E') {
                    x1 = i;
                    y1 = j;
                }
            }
        }
        ans = bfs(x0, y0, x1, y1);
        if (ans <= t && ans >= 0) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}