网格着色游戏:查找绘制的红线和蓝线数。

Question

问题描述: Walter有一个N*M大小的网格，最初每个单元格都是白色的。沃尔特可以画一个水平或垂直的笔画，可以是一个或更长的细胞。沃尔特只用红色画水平笔画，用蓝色画垂直笔画，沃尔特从不画两次水平笔画或两次垂直笔画重叠。如果水平笔划横过垂直笔划，则单元格的颜色为绿色。给定具有细胞颜色模式的字符串，找出实现这一目标所需的红色和蓝色笔画数。

输入：{"GRG"，"BGW"，"WWW"} OP: 2红色和3蓝色笔划

Answer 1

import java.util.*;

public class GridColouring {

    public static int getStrokes(String [] grid) {
        int N = grid.length;
        int M = grid[0].length();
        HashSet<Integer> hr = new HashSet<>();
        HashSet<Integer> v = new HashSet<>();
        int count = 0;
        for (int i = 0; i < N; i++) {
            String row = grid[i];
            row = row.toUpperCase();
            for (int j = 0; j < M; j++) {
                // Precedence of 'and' greater than 'or'
                if (row.charAt(j) == 'G' || (row.charAt(j) == 'R' && !hr.contains(i))) {
                    hr.add(i);

                } else if (hr.contains(i)) {
                    if (j > 0 && grid[i].charAt(j - 1) == 'B') {
                        count++;
                    }
                }
                if (row.charAt(j) == 'G' || (row.charAt(j) == 'B' && !v.contains(j))) {
                    v.add(j);
                } else if(v.contains(j)) {

                    if (i > 0 && grid[i-1].charAt(j) == 'R') {
                        count++;
                    }
                }
            }
        }
        int horStrokes = hr.size();
        int verStrokes = v.size();

        int minStrokes = horStrokes + verStrokes + count;
        return minStrokes;
    }
    public static void main(String [] args) {

        String [] a = {"GR.","BG.","RBR","BBB"};
        System.out.println(getStrokes(a));
    }
}

产出:8

Answer 2

我看不出动态编程会给这件事增加什么。

使每条相邻的红色或绿色像素线成为水平笔划。

使每一列连续的蓝色或绿色像素垂直笔画。

数一数笔画的总数。这复制了最初的模式，也是所需的最小笔画数:每一次笔画都尽可能地扩展，而不与数据相矛盾。