2020小米网络赛第一场 Walking Machine（BFS）

本文主要是介绍2020小米网络赛第一场 Walking Machine（BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
题意：
每个点有一个方向值，代表这个点出发只能走这个方向。
求多少个点出发可以走到棋盘外。

思路：
经典题了吧，直接从外边界bfs进来看能遍历到多少个点。当然遍历的时候我们要记得把每个点的方向值反一下。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>using namespace std;typedef long long ll;const int mod = 1e9 + 7;
const int maxn = 1000 + 7;int n,m;
int vis[maxn][maxn];
char s[maxn][maxn];
int dirx[] = {1,-1,0,0}; //下上右左
int diry[] = {0,0,1,-1};bool check(int x,int y) {if(x < 0 || y < 0 || x > n + 1 || y > m + 1) {return false;}return true;
}
void bfs() {queue<pair<int,int>>q;q.push({0,0});vis[0][0] = 1;while(!q.empty()) {pair<int,int>now = q.front();q.pop();int x = now.first,y = now.second;for(int i = 0;i < 4;i++) {int dx = x + dirx[i];int dy = y + diry[i];if(!check(dx,dy)) continue;if(vis[dx][dy]) continue;if(dx != 0 && dy != 0 && dx != n + 1 && dy != m + 1) {if(i == 0 && s[dx][dy] != 'W') continue;if(i == 1 && s[dx][dy] != 'S') continue;if(i == 2 && s[dx][dy] != 'A') continue;if(i == 3 && s[dx][dy] != 'D') continue;}vis[dx][dy] = 1;q.push({dx,dy});}}
}int main() {scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) {scanf("%s",s[i] + 1);}bfs();int ans = 0;for(int i = 1;i <= n;i++) {for(int j = 1;j <= m;j++) {if(vis[i][j]) {ans++;}}}printf("%d\n",ans);return 0;
}