网格着色游戏：查找绘制的红色和蓝色线条的数量

问题描述：

问题描述：Walter的网格大小为N * M，最初每个单元格都是白色的。沃尔特可以画一个水平或垂直的笔画，长度可以是1或更多。沃尔特只用红色绘制水平笔划，用蓝色绘制垂直笔划沃尔特从不绘制两个水平或两个垂直笔划重叠。如果水平笔画穿过垂直笔画，则单元格的颜色为绿色。给定具有单元格颜色图案的字符串，找到实现它所需的红色和蓝色笔划的数量。网格着色游戏：查找绘制的红色和蓝色线条的数量

输入：{ “广电运通”， “BGW”， “WWW”} OP：2红色和蓝色3中风

答

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

答

我没有看到添加到此什么动态规划。

使每个连续的红色或绿色像素线成为水平笔画。

使每个连续的蓝色或绿色像素列成为垂直笔划。

计算笔划总数。这再现了初始模式，并且是所需笔画的最小数量：每个笔画尽可能延伸，而不会与数据相矛盾。

网格着色游戏：查找绘制的红色和蓝色线条的数量

相关推荐