1247: 彩色的棋子(chess)

题目描述

小S正趴在地上画画，发现书桌上有一个国际象棋棋盘，上面还放了一些棋子。她想用手中的彩笔给这些棋子都涂上颜色，使得每一行或每一列里没有颜色相同的棋子。
小S想知道她至少要用几种彩笔呢？

输入

第一行一个整数N（1≤N≤100），表示国际象棋的棋盘规模是N*N的。
接下来是一个N*N的字符矩阵，由”*”和”.”两种字符组成。如果矩阵中第i行第j列的字符是”*”，则表示棋盘上第i行第j列的格子中有一个棋子；如果是”.”，则那个格子是空着的。

输出

输出一个整数M，表示至少要涂M种颜色。

样例输入

2
*.
**

样例输出

问题重述

我们有一个N×N的国际象棋棋盘，上面有一些棋子（用'*'表示）和空格（用'.'表示）。我们需要给这些棋子涂色，要求：

在同一行或同一列中，没有两个棋子颜色相同。
目标是使用尽可能少的颜色种类。

我们需要计算出满足上述条件的最少颜色数M。

示例分析

给定的示例输入：

2
*.
**

对应的棋盘：

第一行：* .
第二行：* *

即：

(1,1): *
(1,2): .
(2,1): *
(2,2): *

我们需要给(1,1)、(2,1)、(2,2)这三个位置的棋子涂色。

涂色方案：

如果使用一种颜色：
- 涂色： (1,1)=红色, (2,1)=红色, (2,2)=红色。
- 检查：
  - 第一行：(1,1)=红色，无其他棋子，满足。
  - 第二行：(2,1)=红色, (2,2)=红色，同一行有两个红色，违反条件。
- 因此，一种颜色不行。
使用两种颜色：
- 一种可能的涂色：
  - (1,1)=红色, (2,1)=蓝色, (2,2)=红色。
  - 检查：
    - 行：
      - 第一行：只有(1,1)=红色，满足。
      - 第二行：(2,1)=蓝色, (2,2)=红色，无重复颜色，满足。
    - 列：
      - 第一列：(1,1)=红色, (2,1)=蓝色，无重复颜色，满足。
      - 第二列：只有(2,2)=红色，满足。
- 因此，两种颜色可以满足。

所以，最少需要2种颜色。

一般解法

这个问题可以转化为图论中的图着色问题。具体步骤如下：

构建冲突图：
- 将每个棋子看作图中的一个顶点。
- 如果两个棋子在同一行或同一列，则在它们之间画一条边（即它们不能同色）。
求图的最小着色数：
- 图的最小着色数（即最小的颜色数使得相邻顶点不同色）就是这个问题的解。

然而，这种冲突图是一种特殊的图：它是棋盘上棋子的行和列冲突构成的图。这种图实际上是一个二部图的并集，具体来说：

对于行冲突：同一行中的任何两个棋子不能同色。
- 这意味着同一行中的棋子必须彼此不同色。因此，一行中如果有k个棋子，至少需要k种颜色（在这一行内）。
对于列冲突：同一列中的任何两个棋子不能同色。
- 同理，一列中如果有k个棋子，至少需要k种颜色（在这一列内）。

因此，整个问题的最小颜色数是所有行和所有列中棋子数的最大值的最大值。即：

M=max⁡(max number of ’*’ in any row,max number of ’*’ in any column)M=max(max number of ’*’ in any row,max number of ’*’ in any column)

为什么这个公式成立？

假设某一行有k个棋子，那么至少需要k种颜色来区分这一行的棋子（因为它们在同一行不能同色）。
同理，如果某一列有k个棋子，至少需要k种颜色来区分这一列的棋子。
因此，整个棋盘的最小颜色数必须至少是行和列中棋子数的最大值的最大值。
可以构造一种涂色方案，使得颜色数正好是这个最大值（例如，可以使用拉丁方或贪心涂色方法）。

应用到示例

示例：

2
*.
**

行：
- 第一行：1个'*'
- 第二行：2个'*'
- 行最大：2
列：
- 第一列：2个'*'（(1,1)和(2,1)）
- 第二列：1个'*'（(2,2)）
- 列最大：2
因此，M = max(2, 2) = 2。

另一个示例

考虑：

3
*.*
***
*.*

行：
- 第一行：2
- 第二行：3
- 第三行：2
- 行最大：3
列：
- 第一列：3
- 第二列：3
- 第三列：2
- 列最大：3
M = max(3, 3) = 3。

实现步骤

读取输入：
- 读取N。
- 读取N×N的棋盘。
计算每行的'*'的数量，找到最大值。
计算每列的'*'的数量，找到最大值。
输出这两个最大值的较大者。

代码实现

以下是C++的实现代码：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main() {int N;cin >> N;vector<string> board(N);for (int i = 0; i < N; ++i) {cin >> board[i];}int max_row = 0;for (int i = 0; i < N; ++i) {int count = 0;for (int j = 0; j < N; ++j) {if (board[i][j] == '*') {count++;}}max_row = max(max_row, count);}int max_col = 0;for (int j = 0; j < N; ++j) {int count = 0;for (int i = 0; i < N; ++i) {if (board[i][j] == '*') {count++;}}max_col = max(max_col, count);}cout << max(max_row, max_col) << endl;return 0;
}