校园网站怎么做/2022知名品牌营销案例100例

原题地址

https://ac.nowcoder.com/acm/contest/7501/I

解题思路

（其实一开始题目没读懂qwq）
一开始和队友想的方向错了，按照走的顺序来模拟，这样的话TLE了，所以要想一种每个点只需要访问一次的方案。

灵机一动的我发现从出口逆着走就可以了，走过的每个点标记一下，保证每个点只走一次。

但是当时已经累了代码写不出来qwq果然我蒟蒻~

所以这是一道思维+bfs+阅读理解的题~默默补题。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = (a); i < (b); ++i)
#define _rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define pb push_back
#define LOCAL  //提交的时候一定要记得注释掉这句话
#define maxn 1010
#define INF 0x3f3f3f3f
//int label[maxn] = {};
//bool hasV[maxn] = {false};
char t[maxn][maxn];
bool isV[maxn][maxn];
int readint() {int x; scanf("%d", &x); return x;
}struct pos{int x, y;
};int n, m, sum = 0;void bfs(int x, int y) {queue<pos> q;pos now = pos{x, y};q.push(now);while (!q.empty()) {now = q.front();q.pop();if (!isV[now.x][now.y]) {isV[now.x][now.y] = true;sum++;if (now.x + 1 < n && t[now.x + 1][now.y] == 'W') q.push(pos{now.x + 1, now.y});if (now.x - 1 >= 0 && t[now.x - 1][now.y] == 'S') q.push(pos{now.x - 1, now.y});if (now.y + 1 < m && t[now.x][now.y + 1] == 'A') q.push(pos{now.x, now.y + 1});if (now.y - 1 >= 0 && t[now.x][now.y - 1] == 'D') q.push(pos{now.x, now.y - 1});}}
}int main() {
#ifdef LOCALfreopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);  //可以把结果直接打印出来看
#endifscanf("%d%d", &n, &m);getchar();_for(i, 0, n) {_for(j, 0, m) {scanf("%c", &t[i][j]);}getchar();}_for(i, 0, n) {if (t[i][0] == 'A') bfs(i, 0);if (t[i][m - 1] == 'D') bfs(i, m - 1);if (i == 0 && t[0][0] == 'W') bfs(0, 0);if (i == 0 && t[0][m - 1] == 'W') bfs(0, m - 1);if (i == n - 1 && t[n - 1][0] == 'S') bfs(n - 1, 0);if (i == n - 1 && t[n - 1][m - 1] == 'S') bfs(n - 1, m - 1);}_for(i, 1, m - 1) {if (t[0][i] == 'W') bfs(0, i);if (t[n - 1][i] == 'S') bfs(n - 1, i);}printf("%d", sum);return 0;
}