【算法】腾讯模拟题：画家小Q

摘要：题目描述画家小又开始他的艺术创作。每个测试用例的第一行包含两个正整数和表示画板的长宽。接下来的行包含个长度为的字符串其中包含字符分别表示蓝色黄色绿色空白。整个表示小要完成的作品。输出描述输出一个正整数表示小最少需要多少次操作完成绘画。

画家小Q又开始他的艺术创作。小Q拿出了一块有NxM像素格的画板, 画板初始状态是空白的,用"X"表示。
小Q有他独特的绘画技巧,每次小Q会选择一条斜线, 如果斜线的方向形如"/",即斜率为1,小Q会选择这条斜线中的一段格子,都涂画为蓝色,用"B"表示;如果对角线的方向形如"",即斜率为-1,小Q会选择这条斜线中的一段格子,都涂画为黄色,用"Y"表示。
如果一个格子既被蓝色涂画过又被黄色涂画过,那么这个格子就会变成绿色,用"G"表示。
小Q已经有想画出的作品的样子, 请你帮他计算一下他最少需要多少次操作完成这幅画。

每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数N和M(1 <= N, M <= 50), 表示画板的长宽。
接下来的N行包含N个长度为M的字符串, 其中包含字符"B","Y","G","X",分别表示蓝色,黄色,绿色,空白。整个表示小Q要完成的作品。

输出一个正整数, 表示小Q最少需要多少次操作完成绘画。

输入

4 4
YXXB
XYGX
XBYY
BXXY

输出

3

说明

XXXX
XXXX
XXXX
XXXX
->
YXXX
XYXX
XXYX
XXXY
->
YXXB
XYBX
XBYX
BXXY
->
YXXB
XYGX
XBYY
BXXY

https://www.nowcoder.com/ques...

牛客网

从(0,0)位置开始遍历

如果遍历到(i,j)位置为B——>则继续向左下方(i+1,j-1)和右上方(i-1,j+1)
遍历时，遇到将B置为X，遇到G置为（消除B）置为Y
count++;
如果遍历到(i,j)位置为Y——>则继续向左上方(i-1,j-1)和右下方(i+1,j+1)
遍历时，遇到将Y置为X，遇到G置为（消除Y）置为B
count++;
如果遍历到(i,j)位置为G——>则分别执行1,2

import java.util.Scanner; 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String tem = scanner.nextLine();
        int n = Integer.valueOf(tem.split(" ")[0]);
        int m = Integer.valueOf(tem.split(" ")[1]);
        char color[][] = new char[n][m];
        for (int i = 0; i < n; i++) {
            tem = scanner.nextLine();
            for (int j = 0; j < tem.length(); j++) {
                color[i][j] = tem.charAt(j);
            }
        }
 
        getMinStep(n, m, color);
 
        scanner.close();
 
    }
 
    private static void getMinStep(int n, int m, char color[][]) {
 
        int step = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (color[i][j] == "Y") {
                    dray(i, j, n, m, color); 
                    step++;
                } else if (color[i][j] == "B") {
                    drab(i, j, n, m, color); 
                    step++;
                } else if (color[i][j] == "G") {
                    dray(i, j, n, m, color); 
                    step++;
                    drab(i, j, n, m, color); 
                    step++;
                }
            }
        }
 
        System.out.println(step);
    }
    private static void dray(int x, int y, int n, int m, char color[][]) {
       
        if (x >= 0 && x < n && y >= 0 && y < m && (color[x][y] == "Y" || color[x][y] == "G")) {
            if (color[x][y] == "G") {
                color[x][y] = "B"; 
            } else {
                color[x][y] = "X";
            }
 
            dray(x - 1, y - 1, n, m, color);
            dray(x + 1, y + 1, n, m, color);
 
        }
 
    }
 
    private static void drab(int x, int y, int n, int m, char color[][]) {
   
        if (x >= 0 && x < n && y >= 0 && y < m && (color[x][y] == "B" || color[x][y] == "G")) {
            if (color[x][y] == "G") {
                color[x][y] = "Y"; 
            } else {
                color[x][y] = "X"; 
            }
 
            drab(x + 1, y - 1, n, m, color);
            drab(x - 1, y + 1, n, m, color);
 
        }
    }
 
}

while(line=readline()){
    let lines = line.split(" ");
    let n = parseInt(lines[0]);
    let m = parseInt(lines[1]);
    let arr = new Array();
    for(let i = 0; i < n; i++){
        let line2 = readline();
        arr[i] = new Array();
        for(let j = 0; j < m; j++){
            arr[i][j] = line2[j];
            //print(arr[i][j]);
        }
    }
    let step = 0;
    for(let i = 0; i < n; i++){
        for(let j = 0; j < m; j++){
            //print("---------## 访问点(" + i +" , "+ j + " ): " +arr[i][j]);
            if(arr[i][j] == "Y"){
                draw_y(arr, i, j, n, m);
                step++;
            }else if(arr[i][j] == "B"){
                draw_b(arr, i, j, n, m);
                step++;
            }else if(arr[i][j] == "G"){
                draw_y(arr, i, j, n, m);
                step++;
                draw_b(arr, i, j, n, m);
                step++
            }
        }
    }
    print(step);
}
function draw_y(arr,x,y,n,m){
    //print("draw_y:");
    //print(x,y,n,m);
    if(x >= 0 && x < n && y >=0 && y < m && (arr[x][y] == "Y" || arr[x][y] == "G")){
        if(arr[x][y] == "Y"){
            arr[x][y] = "X";
        }else{
            arr[x][y] = "B";
        }
        //print("("+x+","+y+")"+"左上角：");
        draw_y(arr, x-1, y-1, n, m);
        
        //print("("+x+","+y+")"+"右下角：");
        draw_y(arr, x+1, y+1, n, m);
    }
}
function draw_b(arr,i,j,n,m){
    //print("draw_b:");
    //print(i,j,n,m);
    if(i >= 0 && i < n && j >=0 && j < m && (arr[i][j] == "G" || arr[i][j] == "B")){
        if(arr[i][j] == "B"){
            arr[i][j] = "X";
        }else{
            arr[i][j] = "Y";
        }
        
        //print("("+i+","+j+")"+"左下角：");
        draw_b(arr, i-1, j+1, n, m);
        
        //print("("+i+","+j+")"+"右上角：");
        draw_b(arr, i+1,j-1,n,m);
    }
}

一道题调试了一个星期，后来被人提醒，原来是把=写成了==.一直都没发现，修改之后就能通过了QAQ