本文共 2503 字，大约阅读时间需要 8 分钟。

C++ ????????????

????

????????????finding?????????????????????#??????????????????????????????????????????????BFS???????????????????????????????????finding???

????

???????????????

????

????

????

????

#include 
   
    
#include 
    
     
using namespace std;
char map_1[101][101];
int x1, y1, x2, y2;
struct node {
    int x, y;
};
int map_2[101][101];
int x_1[5] = {0, 1, -1, 0, 0};
int x_2[5] = {0, 0, 0, 1, -1};
node q[100001];
int heads = 1, lose = 1;
void push(node a) {
    q[++lose] = a;
}
int BFS() {
    node a;
    a.x = x1, a.y = y1;
    q[1] = a;
    while (heads <= lose) {
        node n = q[heads];
        heads++;
        if (n.x == x2 && n.y == y2) {
            printf("YES\n");
            return 0;
        }
        for (int i = 1; i <= 4; i++) {
            node n1 = n;
            if (!map_2[n1.x + x_1[i]][n1.y + x_2[i]] && map_1[n1.x + x_1[i]][n1.y + x_2[i]] == '.') {
                n1.x += x_1[i];
                n1.y += x_2[i];
                push(n1);
                map_2[n1.x][n1.y] = 1;
            }
        }
    }
    printf("NO\n");
    return 0;
}
int main() {
    int n, m;
    scanf("%d", &n);
    while (n--) {
        memset(map_1, '#', sizeof(map_1));
        memset(map_2, 0, sizeof(map_2));
        heads = lose = 1;
        scanf("%d\n", &m);
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%c", &map_1[i][j]);
            }
            scanf("\n");
        }
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        x1 += 1; y1 += 1; x2 += 1; y2 += 1;
        if (map_1[x1][y1] == '#' || map_1[x2][y2] == '#') {
            printf("NO\n");
            continue;
        }
        BFS();
    }
    return 0;
}
    
   

????

• ?????????????????? map_1 ???????map_2 ??????????
• ??????? x_1 ? x_2 ?????????????????
• BFS??????????????????????????????????????????
• ????????????????????????????????

??

???????????????????finding?????????????????????????????????????????????????????????????????????

转载地址：http://zkpfk.baihongyu.com/