AT_abc348_d [ABC348D] Medicines on Grid 题解

题目传送门

解题思路

这道题目就是简单粗暴的搜索，需要注意的是这道题目最好不要标记，如果你写的是普通的标记，那么我找到了一组 hack 数据。

输入：

1 7
..S...T
2
1 1 114514
1 3 2

输出：

Yes

显然，你不可以从起点出发直接朝终点走去，因为这样到达不了终点。所以你必须得先走到 $(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;
}