提出 #52113953

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define x first
#define y second
#define sz(x) ((int)x.size())
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 210 * 210;

void solve() {
	int n, m;
	cin >> n >> m;
	vector<string> s(n);
	vector<vector<int>> a(n, vector<int>(m));
	vector<vector<int>> f(n, vector<int>(m, -1));
	for(auto &str : s) {
		cin >> str;
	}
	auto can = [&](int x, int y) {
		return x >= 0 && x < n && y >= 0 && y < m && s[x][y] != '#';	
	};
	int cnt;
	cin >> cnt;
	while(cnt--) {
		int x, y, z;
		cin >> x >> y >> z;
		a[x - 1][y - 1] = z;
	}
	
	int stx = 0, sty = 0, edx = 0, edy = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(s[i][j] == 'S') {
				stx = i, sty = j;
			}
			if(s[i][j] == 'T') {
				edx = i, edy = j;
			}
		}
	}
	
	int dx[] = {-1, 0, 1, 0};
	int dy[] = {0, 1, 0, -1};
	auto bfs = [&] {
		queue<PII> q;
		q.push({stx, sty});
		while(q.size()) {
			auto [x, y] = q.front();
			q.pop();
		
			f[x][y] = max(f[x][y], a[x][y]);
			
			for(int i = 0; i < 4; i++) {
				int c = x + dx[i];
				int d = y + dy[i];
				if(can(c, d) && f[c][d] < f[x][y] - 1) {
					f[c][d] = f[x][y] - 1;
					q.push({c, d});
				}
			}
		}
	};
	bfs();
	cout << (f[edx][edy] >= 0 ? "Yes\n" : "No\n");
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t = 1;
//	cin >> t;	
	while(t--) {
		solve();
	}
	return 0;
}

提出情報

ジャッジ結果