前言

本来想等讲评完把第二题补了一起发结果昨天讲评的一言难尽只好只发第一题。

Q1 染色时间

问题描述

小蓝有一个 $n$ 行 $m$ 列的白色棋盘, 棋盘的每一个方格都可以被染成彩色。

每个方格有一个染色时间 t i j t_{i j} tij​, 不同方格的染色时间可能不同。如果一个方 格被触发了染色, 这个方格就会在 t i j t_{i j} tij​ 秒之后变成彩色, 然后将自己上下左右四 个方向相邻的方格触发染色。每个方格只能被触发染色一次, 第一次触发之后 的触发为无效触发。

给定每个方格的染色时间, 在时刻 0 触发第一行第一列的方格染色, 请问 多长时间后整个棋盘完成染色。

输入格式

输入的第一行包含两个整数 $n,m$, 分别表示棋盘的行数和列数。

接下来 $n$ 行, 每行 $m$ 个正整数, 相邻的整数之间用一个空格分隔, 表示每 个方格的染色时间。该部分的第 $i$ 行第 $j$ 个整数表示 t i j t_{i j} tij​, 即第 $i$ 行第 $j$ 列的方 格的染色时间。

输出格式

输出一行包含一个整数, 表示整个棋盘完成染色的时间。

分析:主要是要知道优先队列可以跑这种有要求特定搜索顺序的bfs这个tip其他的就是一个普通的bfs拓宽眼界用的一个题。

/*
* @Author: gorsonpy
* @Date:   2023-01-17 12:57:35
* @Last Modified by:   gorsonpy
* @Last Modified time: 2023-01-18 13:37:08
*/
#include<iostream>
#include<queue>
using namespace std;

using PII = pair<int, int>;
using PIII = pair<int, PII>;
const int N = 510;

int t[N][N], n, m;
bool st[N][N];

#define x first
#define y second

int ans;
int bfs()
{
	int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
	priority_queue<PIII, vector<PIII>, greater<PIII> > q;
	q.push({t[0][0], {0, 0}});
	st[0][0] = true;
	while(q.size())
	{
		auto r = q.top();
		q.pop();

		int timestamp = r.x;
		PII pos = r.y;

		ans = max(ans, timestamp);
		for(int i = 0; i < 4; ++i)
		{
			int nx = pos.x + dx[i], ny = pos.y + dy[i];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if(!st[nx][ny])
			{
				q.push({timestamp + t[nx][ny], {nx, ny}});
				st[nx][ny] = true;
			}
		}
	}
	return ans;
}
int main()
{
	cin >> n >> m;
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j)
			cin >> t[i][j];

	cout << bfs() << endl;
	return 0;
}