题目链接：https://www.dotcpp.com/oj/problem2356.html

    1. import java.util.*;
    3. class Point{
    4.     int x1, y1;
    5.     int x2, y2;
    6.     int color;
    8.     Point(int x1, int y1, int x2, int y2, int color){
    9.         this.x1 = x1;
    10.         this.y1 = y1;
    11.         this.x2 = x2;
    12.         this.y2 = y2;
    13.         this.color = color;
    14.     }
    15. }
    16. public class Test{
    17.     //拿起刷子的最少次数
    18.     public static int ans = Integer.MAX_VALUE;
    19.     //平板的个数
    20.     public static int n;
    21.     public static final int N = 16;
    23.     //存储平板的左上角、右下角坐标，当前平板的yanse
    24.     public static Point[] matrix = new Point[N+1];
    26.     //存储当前平板涂色需要满足的前置平板个数
    27.     //（即只有所有前置平板个数都被涂色后，当前平板才能进行涂色）
    28.     public static int[] ind = new int[N+1];
    30.     //存储当前平板的后续平板（类似图的邻接节点）
    31.     public static int[][] G = new int[N+1][N+1];
    33.     //当前平板的访问情况（防止重复访问）
    34.     public static boolean[] visited = new boolean[N+1];
    36.     //预处理出所有平板的前置平板个数和平板之间的访问顺序
    37.     public static void init(){
    38.         //预处理平板之间涂色先后顺序
    39.         for (int i = 1; i <= n; i++){
    40.             for (int j = 1; j <= n; j++){
    41.                 if(matrix[i].x2 == matrix[j].x1 && !(matrix[i].y1 > matrix[j].y2 || matrix[j].y1 > matrix[i].y2)){
    42.                     //代表平板i涂色后可以访问到平板j
    43.                     G[i][j] = 1;
    44.                     //代表平板j涂色需要满足平板i也涂色
    45.                     //并且可能存在多个前置平板涂色的情况
    46.                     ind[j]++;
    47.                 }
    48.             }
    49.         }
    50.     }
    52.     public static void dfs(int step, int color, int cnt){
    53.         //step: 涂色的次数，最坏情况下，每次只能涂一个平板,最大值为n
    54.         //color: 当前刷子的颜色
    55.         //cnt: 当前拿起刷子的次数
    58.         if(ans <= cnt) //剪枝
    59.             return;
    60.         if(step == n){ //更新最优结果
    61.             ans = cnt;
    62.             return;
    63.         }
    65.         for(int i = 1; i <= n; i++){
    66.             if(!visited[i] && ind[i] == 0){ //没有访问过 并且 前置平板均已涂色
    67.                 visited[i] = true;
    68.                 for(int j = 1; j <= n; j++){
    69.                     if(G[i][j] == 1){
    70.                         ind[j]--;
    71.                     }
    72.                 }
    73.                 if(color == matrix[i].color){ //如果当前平板的颜色与刷子的颜色相同，则不用更换刷子
    74.                     dfs(step + 1, color, cnt);
    75.                 }else{ //否则需要更换刷子，拿起刷子的次数+1
    76.                     dfs(step + 1, matrix[i].color, cnt + 1);
    77.                 }
    79.                 //回溯
    80.                 for(int j = 1; j <= n; j++){
    81.                     if(G[i][j] == 1)
    82.                         ind[j]++;
    83.                 }
    84.                 visited[i] = false;
    85.             }
    86.         }
    87.     }
    88.     public static void main(String[] args) {
    89.         Scanner sc = new Scanner(System.in);
    90.         n = sc.nextInt();
    91.         int x1, x2, y1, y2, color;
    92.         for(int i = 1; i <= n; i++){
    93.             x1 = sc.nextInt();
    94.             y1 = sc.nextInt();
    95.             x2 = sc.nextInt();
    96.             y2 = sc.nextInt();
    97.             color = sc.nextInt();
    98.             matrix[i] = new Point(x1, y1, x2, y2, color);
    99.         }
    100.         //预处理
    101.         init();
    103.         //从左上角进行搜索
    104.         //并且递归入口是没有使用刷子的
    105.         dfs(0, 0, 0);
    107.         System.out.println(ans);
    108.     }
    109. }