求助!BFS只错1个点
查看原帖
求助!BFS只错1个点
787131
VictorTang楼主2024/4/13 22:05
#include<iostream>
#include<queue>
#include<map>
using namespace std;

int n, m, s, t, u, v, h, w, k, e;
char c[205][205];
int g[205][205];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

struct Grid {
	int x, y, energy;
} SPECIAL[1];

queue<Grid> q;
map<pair<int, int>, int> visited;

bool solve(){
	q.push({s, t, 0});
	
	bool ans = false;
	while (!q.empty()){
		auto cur = q.front();
		q.pop();
		
		if (cur.x == u and cur.y == v)
			ans |= (cur.energy >= 0);
		
		for (int d=0; d<4; d++){
			int newX = dx[d] + cur.x;
			int newY = dy[d] + cur.y;
			if (newX < 1 or newX > n
			 or newY < 1 or newY > m
			 or c[newX][newY] == '#') continue;
			 
			int ret = max(g[cur.x][cur.y], cur.energy) - 1;
			if (ret < 0) continue;
			
			if (visited.count({newX, newY}))
				if (visited[{newX, newY}] >= ret) continue;
			visited[{newX, newY}] = ret;
			q.push({newX, newY, ret});
		}
	}
	
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	
	cin >> n >> m;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			cin >> c[i][j];
			if (c[i][j] == 'S')
				s = i, t = j;
			if (c[i][j] == 'T')
				u = i, v = j;
		}
	}
	
	cin >> k;
	for (int i=0; i<k; i++){
		cin >> h >> w >> e;
		g[h][w] = e;
	}
	
	if (solve()) cout << "Yes";
	else cout << "No";
}	// Victor Tang
2024/4/13 22:05
加载中...