涂国旗（洛谷P3392题题解，Java语言描述）

题目要求

题目链接

分析

我做的就比较暴力啦，由于三种颜色都至少有一行，所以：

• W ： [ 0 , N − 2 ) W：[0, N-2) W：[0,N−2)
• B ： [ 1 , N − 1 ) B： [1, N-1) B：[1,N−1)
• R ： [ 2 , N ) R： [2, N) R：[2,N)

这是最极限的情况，也是理论上的情况，实际上 B B B被 W W W约束着， R R R被 B B B直接约束且被 W W W间接约束。

我们的暴力循环需要定的就是 W W W的右边界以及基于 W W W右边界的 B B B右边界。

由于是取最小值，所以初始化的 m i n min min值要定的大一些，比如0x7fffffff。

暴力循环下来，算法的时间复杂度为 O ( n 3 ∗ m ) O(n^3*m) O(n3∗m)。

先循环 i i i和 j j j，再内部循环白、蓝、红，千万别搞错。

更优解 → O ( n 2 + n m ) O(n^2+nm) O(n2+nm)算法

AC代码（Java语言描述）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = reader.readLine().split("\\s+");
        int n = Integer.parseInt(line1[0]), m = Integer.parseInt(line1[1]);
        char[][] graph = new char[n][m];
        for (int i = 0; i