题目传送门
解题思路
这道题目就是简单粗暴的搜索,需要注意的是这道题目最好不要标记,如果你写的是普通的标记,那么我找到了一组 hack 数据。
输入:
1 7
..S...T
2
1 1 114514
1 3 2
输出:
Yes
显然,你不可以从起点出发直接朝终点走去,因为这样到达不了终点。所以你必须得先走到
(
1
,
1
)
(1,1)
(1,1) 得到能量再朝终点走去,但是在往返途中,你会经过你之前走过的点,因此你不能进行标记,除非你判断此点是否被走过两次以上但是一般不会这样。
CODE:
#include <bits/stdc++.h>
using namespace std;
//#define int long long
int h, w, sx, sy, ex, ey;
char c[410][410];
int a[410][410], ans[410][410];
struct node{
int x, y;
int nengliang;
};
int dx[] = {0, -1, 1, 0};
int dy[] = {1, 0, 0, -1};
queue<node> q;
void bfs() {
q.push({sx, sy, a[sx][sy]});
while (!q.empty()) {
node t = q.front();
q.pop();
if (t.nengliang < 0)
continue;
if (t.x == ex && t.y == ey) {
cout << "Yes";
return;
}
if (t.nengliang == 0)
continue;
if (ans[t.x][t.y]) {
if (t.nengliang > ans[t.x][t.y])
ans[t.x][t.y] = t.nengliang;
else
continue;
}
else
ans[t.x][t.y] = t.nengliang;
for (int i = 0; i < 4; i++) {
int xx = t.x + dx[i];
int yy = t.y + dy[i];
if (xx > 0 && xx <= h && yy > 0 && yy <= w && c[xx][yy] != '#') {
node d = t;
if (t.nengliang - 1 >= a[xx][yy])
d.nengliang--;
else
d.nengliang = a[xx][yy];
d.x = xx;
d.y = yy;
q.push(d);
}
}
}
cout << "No";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> h >> w;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> c[i][j];
if (c[i][j] == 'S') {
sx = i, sy = j;
}
if (c[i][j] == 'T') {
ex = i, ey = j;
}
}
}
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int r, c, e;
cin >> r >> c >> e;
a[r][c] = e;
}
bfs();
return 0;
}