题目大意

给定一个字符型二维数组，给定$n,m$ 作为边界，给定$sx,sy$作为起点，$fx,fy$作为终点。需要判断能否从$( sx, sy )$走到$( fx, fy )$，可以输出 $YES$， 不可以输出 $NO$。

---

输入格式

第一行两个整数$n,m$，第二行四个整数$sx,sy,fx,fy$，接下来$n$行，每行输入$m$个字符。

---

输出格式

一行，$YES$或$NO$。

---

思路&代码实现

使用广度优先搜索和深度优先搜索都可以。

1.定义

定义$n,m,sx,sy,fx,fy$,字符数组$a$,方向数组$dirx,diry$,标记数组$vis$和一个$void$类型的$bfs$函数,给定两个参数$x,y$。($dfs$函数也可以)。使用$bfs$函数需要定义结构体$node$。

struct node{
    int x, y;
};
int n,m;
int sx,sy,fx,fy;
char a[50][50];
int dirx[10] = {1,-1,0,0};
int diry[10] = {0,0,1,-1};
int vis[50][50];
void bfs( int x, int y ){
    
}

2.输入

输入$n,m,sx,sy,fx,fy$和字符二维数组$a$。

cin >> n >> m >> sx >> sy >> fx >> fy;
for ( int i = 1; i <= n; i++ ){
    for ( int j = 1; j <= m; j++ ){
        cin >> a[i][j];
    }
}

3.定义$bfs$函数

1.先在$bfs$函数里定义一个$node$类型的队列$q$

queue<node> q;

2.把$bfs$函数的两个参数$x,y$入队

q.push({x,y}); //注意，入队时要加大括号

3.标记$(x,y)$为已走过

vis[x][y] = 1;

4.写一个$while$循环，当$q$不为空时，就重复取队首并出队。

while ( q.size() ){
    node f = q.front(); //使用node类型
    q.pop();
}

5.每次判定是否为终点，是则输出$YES$并结束函数，不是则继续执行

if ( f.x == fx && f.y == fy ){
    cout << "YES";
    return ;
}

6.遍历当前位置的上下左右邻居，如果合法，就入队到$q$里，并标记这个点已走过

for ( int i = 0; i < 4; i++ ){
    int nx = f.x + dirx[i];
    int ny = f.y + diry[i];
    if ( nx >= 1 && ny >= 1 && nx <= n && ny <= m && a[nx][ny] == '.' && vis[nx][ny] == 0 ){
            q.push({nx,ny});
            vis[nx][ny] = 1;
    }
}

7.若循环结束，还没有输出，则是不能走到终点，输出$NO$

cout << "NO";
return ;

8.完整代码

void bfs( int x, int y ){
    queue<node> q;
    q.push({x,y});
    vis[x][y] = 1;
    while ( q.size() ){
        node f = q.front();
        q.pop();
        if ( f.x == fx && f.y == fy ){
            cout << "YES";
            return ;
        }
        for ( int i = 0; i < 4; i++ ){
            int nx = f.x + dirx[i];
            int ny = f.y + diry[i];
            if ( nx >= 1 && ny >= 1 && nx <= n && ny <= m && a[nx][ny] == '.' && vis[nx][ny] == 0 ){
                q.push({nx,ny});
                vis[nx][ny] = 1;
            }
        }
    }
    cout << "NO";
    return ;
}

4.调用函数

在主函数里调用$bfs$,参数为$sx,sy$。

bfs(sx,sy);

5.完整代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x, y;
};
int n,m;
int sx,sy,fx,fy;
char a[50][50];
int dirx[10] = {1,-1,0,0};
int diry[10] = {0,0,1,-1};
int vis[50][50];
void bfs( int x, int y ){
    queue<node> q;
    q.push({x,y});
    vis[x][y] = 1;
    while ( q.size() ){
        node f = q.front();
        q.pop();
        if ( f.x == fx && f.y == fy ){
            cout << "YES";
            return ;
        }
        for ( int i = 0; i < 4; i++ ){
            int nx = f.x + dirx[i];
            int ny = f.y + diry[i];
            if ( nx >= 1 && ny >= 1 && nx <= n && ny <= m && a[nx][ny] == '.' && vis[nx][ny] == 0 ){
                q.push({nx,ny});
                vis[nx][ny] = 1;
            }
        }
    }
    cout << "NO";
    return ;
}
int main(){
    cin >> n >> m >> sx >> sy >> fx >> fy;
    for ( int i = 1; i <= n; i++ ){
        for ( int j = 1; j <= m; j++ ){
            cin >> a[i][j];
        }
    }
    bfs(sx,sy);
    return 0;
}

最后

制作不易，点个赞呗