题目链接
https://www.nowcoder.com/acm/contest/93/D
思路 BFS模板题
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 5e2 + 5; const int MOD = 1e9 + 7; char Map[maxn][maxn]; int flag; int n, m; int Move[][2] = { -1, 0, // up 1, 0, // down 0,-1, // left 0, 1, // right }; bool in_range(int x, int y) { return (x >= 0 && x < n && y >= 0 && y < m); } queue <pii> q; void bfs() { int len = q.size(); for (int i = 0; i < len; i++) { int x = q.front().first, y = q.front().second; q.pop(); Map[x][y] = 'x'; for (int j = 0; j < 4; j++) { int next_x = x + Move[j][0]; int next_y = y + Move[j][1]; if (in_range(next_x, next_y) && Map[next_x][next_y] != 'x') { if (Map[next_x][next_y] == 't') { flag = 1; return; } else { Map[next_x][next_y] = 'x'; q.push(pii(next_x, next_y)); } } } } if (q.size()) bfs(); } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d ", &n, &m); int x = -1, y = -1; for (int i = 0; i < n; i++) { scanf("%s", Map[i]); if (x == -1) for (int j = 0; j < m; j++) { if (Map[i][j] == 's') x = i, y = j; } } while (!q.empty()) q. pop(); q.push(pii(x, y)); //cout << q.size() << endl; flag = 0; bfs(); //for (int i = 0; i < n; i++) // printf("%s\n", Map[i]); if (flag) printf("YES\n"); else printf("NO\n"); } }转载于:https://www.cnblogs.com/Dup4/p/9433152.html
相关资源：JAVA上百实例源码以及开源项目