📝 题目大意

给定一个 $H \times W$ 的网格，部分格子已涂上颜色 1~5，其余格子为空（.）。你需要将所有空格子涂上 1~5 中的一种颜色，使得任意相邻（上下左右）的格子颜色不同。已涂色的格子不能修改。

💡 解题思路

1. 题目分析：网格图中每个格子最多有 4 个相邻格子（上下左右），而我们手上有 5 种颜色可用。根据鸽巢原理，对于任意一个空格子，其周围最多有 4 种不同颜色，因此至少存在一种颜色可以被使用。这保证了贪心策略一定可行。

2. 算法推导：采用贪心着色策略。按行优先顺序遍历所有格子，对于每个空格子，从小到大尝试颜色 1、2、3、4、5，选择第一个未被其四个邻居使用的颜色填入即可。

   • 正确性证明：网格图的最大度数为 4，而我们拥有 5 种颜色。在贪心着色的每一步，当前格子最多有 4 个已着色的邻居（因为遍历顺序为行优先，上方和左方的邻居可能已被着色，下方和右方仍是空格或原始颜色），因此 5 种颜色中至少有一种未被邻居占用。该算法本质上是"最大度 $\Delta = 4$ 的图可以用 $\Delta+1 = 5$ 种颜色贪心着色"这一经典结论的直接应用。
   • 代码中 a 数组为 char a[910][910]，采用 1-indexed 存储，未初始化的边界位置默认为 '\0'（空字符），与任何颜色字符 '1'~'5' 都不相等，因此边界判断自然正确，无需额外处理。

3. 边界与细节：

   • 数组大小开到 $910 \times 910$，足以容纳 $H, W \leq 500$ 的输入并留出边界余量。
   • 颜色尝试顺序为 1→2→3→4→5，虽然任意顺序都能保证正确性，但固定顺序保证了输出的确定性。
   • 已涂色的格子直接跳过（if(a[i][j]=='.')），不做任何修改。
   • 注意输入中颜色字符之间无空格，需要用 char 逐个读取。

⏱️ 复杂度分析

• 时间复杂度：遍历每个格子一次，对每个空格子至多检查 5 种颜色 × 4 个方向 = 20 次比较，因此总复杂度为 $O(H \times W)$。
• 空间复杂度：仅使用一个 $910 \times 910$ 的 char 数组存储网格，空间复杂度为 $O(H \times W)$。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
char a[910][910];  // 开大数组，1-indexed，边界默认为 '\0'
int main()
{
	int n,m;cin>>n>>m;
	// 读入原始网格
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	// 贪心着色：按行优先遍历，对每个空格尝试颜色 1~5
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]=='.')
			{
				// 尝试颜色 1：检查四个邻居是否都不为 '1'
				if(a[i+1][j]!='1'&&a[i-1][j]!='1'&&a[i][j+1]!='1'&&a[i][j-1]!='1'){a[i][j]='1';continue;}
				// 尝试颜色 2
				if(a[i+1][j]!='2'&&a[i-1][j]!='2'&&a[i][j+1]!='2'&&a[i][j-1]!='2'){a[i][j]='2';continue;}
				// 尝试颜色 3
				if(a[i+1][j]!='3'&&a[i-1][j]!='3'&&a[i][j+1]!='3'&&a[i][j-1]!='3'){a[i][j]='3';continue;}
				// 尝试颜色 4
				if(a[i+1][j]!='4'&&a[i-1][j]!='4'&&a[i][j+1]!='4'&&a[i][j-1]!='4'){a[i][j]='4';continue;}
				// 尝试颜色 5（由鸽巢原理，必然成功）
				if(a[i+1][j]!='5'&&a[i-1][j]!='5'&&a[i][j+1]!='5'&&a[i][j-1]!='5'){a[i][j]='5';continue;}
			}
		}
	}
	// 输出结果
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cout<<a[i][j];
		puts("");
	}
}