自闭中——悲伤往事12.20

题2. 在一个地图上有若干个基站，每个基站有不同的信号强度，假设每远离基站一个单元，信号强度就减少1，那么非基站点上的信号强度就是周围基站提供信号的最大值。有一个机器人想从地图左上角走到右下角，需要满足每个点上都不小于机器人接受信号的阈值Th。试求机器人运动的最短路径长度。

信号阈值：Th

地图大小：行-N 列-M

基站数量：K

X1 Y1 Len1：表示处于（X1,Y1）的基站信号强度为Len1

示例：

输入：

1

4 4

2

0 1 2

3 2 3

该问题可分成两个子问题：

一是求解地图上的信号强度分布（BFS）

二是根据信号分布确定可行节点，进而通过（BFS）来寻找最短路

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

queue<pair<int, int>> q;
vector<int> dx = {1,0,-1,0};
vector<int> dy = {0,1,0,-1};
int N, M;
vector<vector<int>> grid_len(vector<vector<int>>& grid, vector<vector<int>>& vis) {
	while (!q.empty()) {
		auto XY = q.front();
		int x = XY.first, y = XY.second;
		int len_temp = grid[x][y];
		q.pop();
		for (int i = 0; i < 4; i++) {
			if (x + dx[i]<0 || x + dx[i] > M - 1 || y + dy[i]<0 || y + dy[i]>N - 1 || !vis[x + dx[i]][y + dy[i]] || len_temp <=0) {

			}
			else {
				grid[x + dx[i]][y + dy[i]] = len_temp - 1;
				q.push({ x + dx[i], y + dy[i] });
				vis[x + dx[i]][y + dy[i]] = false;
			}
		}
	}
	return grid;
}


int BFS(int pace, vector<vector<int>>& grid, vector<vector<int>>& vis, queue<pair<int, int>> &q) {
	if (q.empty() || vis[N - 1][M - 1] == false) {
		if (pace < N + M - 2) {
			return 0;
		}
		else {
			return pace;
		}
	}
	queue<pair<int, int>> q_temp;
	while (vis[N - 1][M - 1] == true&& !q.empty()) {
		auto XY = q.front();
		int x = XY.first, y = XY.second;
		//int len_temp = grid[x][y];
		q.pop();
		for (int i = 0; i < 4; i++) {
			if (x + dx[i]<0 || x + dx[i] > M - 1 || y + dy[i]<0 || y + dy[i]>N - 1 || !vis[x + dx[i]][y + dy[i]] || grid[x + dx[i]][y + dy[i]] == 0) {

			}
			else {
				//grid[x + dx[i]][y + dy[i]] = len_temp - 1;
				q_temp.push({ x + dx[i], y + dy[i] });
				vis[x + dx[i]][y + dy[i]] = false;
			}
		}
	}
	return BFS(pace + 1, grid, vis, q_temp);
}

int main(){
	int Th; cin >> Th;
	cin >> N >> M;
	int path_max = N + M - 2;
	int K; cin >> K;
	vector<int> state_len;
	vector<pair<int, int>> state;
	for (int i = 0; i < K; i++) {
		int x, y; cin >> x >> y;
		state.push_back({ x,y });
		int len; cin >> len;
		state_len.push_back(len);
	}


	//第一步：遍历地图，得到全地图的信号量
	vector<vector<int>> grid(N, vector<int>(M, 0));
	//验证单个站点所发射的信号强度
	//vector<vector<int>> grid_temp(N, vector<int>(M, 0));
	//vector<vector<int>> vis(N, vector<int>(M, true));

	//grid_temp[state[0].first][state[0].second] = state_len[0];
	//vis[state[0].first][state[0].second] = false;
	//q.push(state[0]);
	//grid_temp = grid_len(grid_temp, vis);

	for (int i = 0; i < K; i++) {
		vector<vector<int>> grid_temp(N, vector<int>(M, 0));
		vector<vector<int>> vis(N, vector<int>(M, true));
		if (grid[state[i].first][state[i].second] < state_len[i]) {
			grid_temp[state[i].first][state[i].second] = state_len[i];
			vis[state[i].first][state[i].second] = false;
			q.push(state[i]);
			grid_temp = grid_len(grid_temp, vis);
		}
		//grid对grid_temp取极大值
		for (int i=0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				grid[i][j] = max(grid[i][j], grid_temp[i][j]);
			}
		}
	}
	//输出
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout<<grid[i][j];
		}
		cout << '\n';
	}

	//第二步：层序遍历，寻找最短路
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			grid[i][j] = grid[i][j]>=Th?1:0;
			cout << grid[i][j];
		}
		cout << '\n';
	}
	vector<vector<int>> visit(N, vector<int>(M, true));
	visit[0][0] = false;
	if (!q.empty()) q.pop();
	q.push({ 0,0 });
	int short_pace;
	//对出发点进行判断
	if (grid[0][0] == 0 || grid[N - 1][M - 1] == 0) {
		short_pace = 0;
	}else{
		short_pace = BFS(0, grid, visit, q);
	}
	cout << '\n' << short_pace;
	return 0;
}

//输入：1 4 4 2 0 1 2 3 2 3
//输入：1 4 4 9 0 0 1 1 0 1 1 1 1 1 2 1 0 2 1 0 3 1 1 3 1 2 3 1 3 3 1
//输入：1 5 5 10 0 0 1 1 0 1 2 0 1 3 0 1 4 0 1 4 1 1 4 2 1 3 2 1 3 3 1 3 4 1 4 4 1