画家小Q

每画一步追求最大连笔，同时将已经画了某种颜色的格子元素设置为下一步需要画的颜色，如原Y画了Y下一步不需要再画设置为X.

package com.plf.tencent;

import java.util.Scanner;

public class XiaoQDrawer {

    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();

    }

    /**
     * 获取最小步数 每画一个线直到颜色不同为止
     * 
     * @param n
     * @param m
     * @param color
     */
    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') {
                    dfs_y(i, j, n, m, color); // 画y
                    step++;
                } else if (color[i][j] == 'B') {
                    dfs_b(i, j, n, m, color); // 画B
                    step++;
                } else if (color[i][j] == 'G') {
                    dfs_y(i, j, n, m, color); // 先画y
                    step++;
                    dfs_b(i, j, n, m, color); // 在画B
                    step++;
                }
            }
        }

        System.out.println(step);
    }

    /**
     * 当前位置画y,是否在后续位置继续画y
     * 
     * @param x
     * @param y
     */
    private static void dfs_y(int x, int y, int n, int m, char color[][]) {
        // 根据要求决定当前位置是否能画y
        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'; // 如果当前位置要求画的是G,那么画了Y之后下一次只能画B
            } else {
                color[x][y] = 'X'; // 如果当前位置要求画的是Y,那么画了Y之后下一次不需要再画
            }

            // 是否连笔继续画，Y对应的是画\，即左上或者右下
            dfs_y(x - 1, y - 1, n, m, color);
            dfs_y(x + 1, y + 1, n, m, color);

        }

    }

    /**
     * 当前位置画B,是否在后续位置继续画B
     * 
     * @param x
     * @param y
     */
    private static void dfs_b(int x, int y, int n, int m, char color[][]) {
        // 根据要求决定当前位置是否能画B
        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'; // 如果当前位置要求画的是G,那么画了Y之后下一次只能画Y
            } else {
                color[x][y] = 'X'; // 如果当前位置要求画的是B,那么画了B之后下一次不需要再画
            }

            // 是否连笔继续画，B对应的是画/，即左下或者右上
            dfs_b(x + 1, y - 1, n, m, color);
            dfs_b(x - 1, y + 1, n, m, color);

        }
    }

}

思路还是比较明确的，一遍AC了。
最求的是一笔尽可能给多个格子上色，然后主要分两种上色方案，如代码所示，有另一个矩阵记录当前位置，是否在之前已经被访问过。

n,m = map(int, input().split())
graph = []
for i in range(n):
    color = input()
    graph.append(color)
visited = [[0] * m for _ in range(n)]
def colorY(i,j,visited,graph):
    while i < n and j < m:
        if graph[i][j] == 'G' or graph[i][j] == 'Y':
            visited[i][j] += 1
            i += 1
            j += 1
        else:
            break
def colorB(i,j,visited,graph):
    while i < n and j >= 0:
        if graph[i][j] == 'G' or graph[i][j] == 'B':
            visited[i][j] += 2
            i += 1
            j -= 1
        else:
            break
res = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'Y' and visited[i][j] == 0:
            colorY(i,j,visited,graph)
            res += 1
        if graph[i][j] == 'B' and visited[i][j] == 0:
            colorB(i,j,visited,graph)
            res += 1
        if graph[i][j] == 'G' and visited[i][j] == 0:
            colorY(i, j, visited, graph)
            colorB(i, j, visited, graph)
            res += 2
        if graph[i][j] == 'G' and visited[i][j] == 1:
            colorB(i, j, visited, graph)
            res += 1
        if graph[i][j] == 'G' and visited[i][j] == 2:
            colorY(i, j, visited, graph)
            res += 1
print(res)

#思路，先读入数据，用一个矩阵存1、2、3代表三种颜色，3同时表示1、2，并且保存1、2的位置信息
#利用堆栈，遍历所有规定方向上的1、2，把每一个连通域记下，最后输出连通域数量即可

n, m = input().split()
n, m = int(n), int(m)
 matrix = [[None for i in range(m)] for j in range(n)]
 dic = {"0":[],"1":[],"2":[]}
 for i in range(n):
 line = input()
 for j in range(len(line)):
 if line[j] == "X":
 matrix[i][j] = 0
 dic["0"].append([i,j])
 elif line[j] == "B":
 matrix[i][j] = 1
 dic["1"].append([i,j])
 elif line[j] == "Y":
 matrix[i][j] = 2
 dic["2"].append([i,j])
 else:
 matrix[i][j] = 3
 dic["1"].append([i,j])
 dic["2"].append([i,j])
 def in_list(li, a):
 #print(li, a)
 for i in range(len(li)):
 if li[i] == a:
 return i
 return None
 draw = []
 while len(dic["1"]):
 stack = []
 temp = []
 t0 = dic["1"].pop(0)
 stack.append(t0)
 while len(stack):
 t = stack.pop(0)
 temp.append(t)
 if t[0] - 1>=0 and t[1] + 1 < m and (matrix[t[0] - 1][t[1] + 1] == 1 or matrix[t[0] - 1][t[1] + 1] == 3):
 ind = in_list(dic["1"], [t[0] - 1, t[1] + 1])
 if ind != None:
 stack.append(dic["1"][ind])
 dic["1"].pop(ind)
 if t[0] + 1 < m and t[1]- 1>=0 and (matrix[t[0] + 1][t[1]- 1] == 1 or matrix[t[0] + 1][t[1] - 1] == 3):
 ind = in_list(dic["1"], [t[0] + 1, t[1] - 1])
 if ind != None:
 stack.append(dic["1"][ind])
 dic["1"].pop(ind)
 draw.append(temp)
 while len(dic["2"]):
 stack = []
 temp = []
 t0 = dic["2"].pop(0)
 stack.append(t0)
 while len(stack):
 t = stack.pop(0)
 temp.append(t)
 if t[0] - 1 >= 0 and t[1] - 1>=0 and (matrix[t[0] - 1][t[1] - 1] == 2 or matrix[t[0] - 1][t[1] - 1] == 3):
 ind = in_list(dic["2"], [t[0] - 1, t[1] - 1])
 if ind != None:
 stack.append(dic["2"][ind])
 dic["2"].pop(ind)
 if t[0] + 1 < m and t[1] + 1 < m and (matrix[t[0] + 1][t[1]+ 1] == 2 or matrix[t[0] + 1][t[1] + 1] == 3):
 ind = in_list(dic["2"], [t[0] + 1, t[1] + 1])
 if ind != None:
 stack.append(dic["2"][ind])
 dic["2"].pop(ind)
 draw.append(temp)
 #print(draw)

print(len(draw))

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        //int N=sc.nextInt();
        //int M=sc.nextInt();
        String TempStr=sc.nextLine();
        int N=Integer.valueOf(TempStr.split(" ")[0]);
        int M=Integer.valueOf(TempStr.split(" ")[1]);
        char[][] Color=new char[N][M];
        int[][] HaveDraw=new int[N][M];
        for(int k1=0;k1<N;k1++){
            TempStr=sc.nextLine();
            for(int k2=0;k2<M;k2++){
                Color[k1][k2]=(TempStr.charAt(k2));
            }
        }
        //int N=4;
        //int M=4;
        //int[][] HaveDraw=new int[N][M];
        //char[][] Color=new char[N][M];
        //char[][] Color= {
        		//{'Y','X','X','B'},
        		//{'X','Y','G','X'},
        		//{'X','B','Y','Y'},
        		//{'B','X','X','Y'}
        		//};
		
        int count=0;
        for(int k1=0;k1<N;k1++){
            for(int k2=0;k2<M;k2++){
                if(Color[k1][k2]=='Y'&&HaveDraw[k1][k2]==0){
                    HaveDraw[k1][k2]+=1;
                    int i=k1,j=k2;
                    while(i<N-1&&j<M-1){
                        i++;
                        j++;
                        if(Color[i][j]=='Y'|Color[i][j]=='G'){
                            HaveDraw[i][j]+=1;
                        }
                        else{
                            break;
                        }
                    }
                    count++;
                }
                
                else if(Color[k1][k2]=='B'&&HaveDraw[k1][k2]==0){
                    HaveDraw[k1][k2]+=2;
                    int i=k1,j=k2;
                    while(i<N-1&&j>0){
                        i++;
                        j--;
                        if(Color[i][j]=='B'|Color[i][j]=='G'){
                            HaveDraw[i][j]+=2;
                        }
                        else{
                            break;
                        }
                    }
                    count++;
                }
                
                else if(Color[k1][k2]=='G'){
                    if(HaveDraw[k1][k2]==0){
                        HaveDraw[k1][k2]=HaveDraw[k1][k2]+3;
                        int i=k1,j=k2;
                        int k=k1,h=k2;
                        while(i<N-1&&j<M-1){
                            i++;
                            j++;
                            if(Color[i][j]=='Y'|Color[i][j]=='G'){
                                HaveDraw[i][j]+=1;
                            }
                            else{
                                break;
                            }
                        }
                        while(k<N-1&&h>0){
                            k++;
                            h--;
                            if(Color[k][h]=='B'|Color[k][h]=='G'){
                                HaveDraw[k][h]+=2;
                            }
                            else{
                                break;
                            }
                        }
                        count=count+2;
                    }
                    else if(HaveDraw[k1][k2]==1){
                        HaveDraw[k1][k2]+=2;
                        int i=k1,j=k2;
                        while(i<N-1&&j>0) {
                        	i++;
                        	j--;
                        	if(Color[i][j]=='B'|Color[i][j]=='G') {
                        		HaveDraw[i][j]+=2;
                        	}
                        	else {
                        		break;
                        	}
                        }
                        count++;
                    }
                    else if(HaveDraw[k1][k2]==2) {
                    	HaveDraw[k1][k2]+=1;
                        int i=k1,j=k2;
                        while(i<N-1&&j<M-1) {
                        	i++;
                        	j++;
                        	if(Color[i][j]=='Y'|Color[i][j]=='G') {
                        		HaveDraw[i][j]+=1;
                        	}
                        	else {
                        		break;
                        	}
                        }
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
    }
}

import sys
raw_input = []
rows, cols = map(int, sys.stdin.readline().split())
for line in sys.stdin:
    raw_input.append(line.rstrip())
mydic = {'Y':[], 'B':[]}
for row in range(rows):
    for col in range(cols):
        if raw_input[row][col] == 'G':
            mydic['Y'].append([row, col])
            mydic['B'].append([row, col])
        elif raw_input[row][col] != 'X':
            mydic[raw_input[row][col]].append([row, col])

if __name__ == '__main__':
    res = 0
    def func(pos, f):
        pivot = pos.pop(0)
        tmp = []
        while pos:
            ele = pos.pop(0)
            if ele[0]-pivot[0] == 1 and ((f == 'B' and pivot[1]-ele[1] == 1) or (f == 'Y' and ele[1]-pivot[1] == 1)):
                pivot = ele
            else:
                tmp.append(ele)
        return tmp
    while mydic['Y'] or mydic['B']:
        if mydic['Y']:
            res += 1
            mydic['Y'] = func(mydic['Y'], 'Y')
        if mydic['B']:
            res += 1
            mydic['B'] = func(mydic['B'], 'B')
    print(res)

import java.util.Arrays;
import java.util.Scanner;

public class DrawerQ {

    public static int count = 0;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            char[][] chs = new char[n][m];
            char[][] temp = new char[n][m];
            for (int i = 0; i < n; i++) {
                String s = sc.next();
                for (int j = 0; j < m; j++) {
                    chs[i][j] = s.charAt(j);
                }
                Arrays.fill(temp[i], 'X');
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (chs[i][j] != temp[i][j]) {
                        if (chs[i][j] == 'Y' || (chs[i][j] == 'G' && temp[i][j] == 'B')) {
                            right(temp, chs, i, j);
                            count ++;
                        }else if (chs[i][j] == 'B' || (chs[i][j] == 'G' && temp[i][j] == 'Y')) {
                            left(temp, chs, i, j);
                            count ++;
                        }else if(chs[i][j] == 'G') {
                            right(temp, chs, i, j);
                            left(temp, chs, i, j);
                            count += 2;
                        }
                    }
                }
            }
            System.out.println(count);
        }
        sc.close();

    }

    public static void right(char[][] temp, char[][] chs, int i, int j) {
        while(i >= 0 && i < temp.length && j >= 0 && j < temp[0].length) {
            if (chs[i][j] == 'Y' && temp[i][j] == 'X') {
                temp[i][j] = 'Y';
            } else if (chs[i][j] == 'G') {
                if(temp[i][j] == 'B') {
                    temp[i][j] = 'G';
                }else if(temp[i][j] == 'X') {
                    temp[i][j] = 'Y';
                }
            } else {
                break;
            }
            i ++;
            j ++;
        }
    }

    public static void left(char[][] temp, char[][] chs, int i, int j) {
        while(i >= 0 && i < temp.length && j >= 0 && j < temp[0].length) {
            if (chs[i][j] == 'B' && temp[i][j] == 'X') {
                temp[i][j] = 'B';
            } else if (chs[i][j] == 'G') {
                if(temp[i][j] == 'Y') {
                    temp[i][j] = 'G';
                }else if(temp[i][j] == 'X'){
                    temp[i][j] = 'B';
                }
            } else {
                break;
            }
            i ++;
            j --;
        }
    }

}

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

#获取输入
N, M = map(int, input().split()) # N*M的画板，N是长，M是宽
pad = [] # 画板,pad[N][M]
for n in range(N):
    pad.append(list(input())) # 'YXXB' -> ['Y', 'X', 'X', 'B']


#算法部分
res = 0
for n, row in enumerate(pad):
    for m, color in enumerate(row):
        if color=='Y'&nbs***bsp;color=='B':
            # print(pad)
            res += 1  # 如果不是空白，则肯定被画了一笔
        if color== 'G':
            res += 2
            pad[n][m] = 'X'
            # \掉Y
            tmp_n = n+1
            tmp_m = m+1
            if tmp_n==N&nbs***bsp;tmp_m==M: # 避免越界
                pass
            else:
                while pad[tmp_n][tmp_m]=='Y'&nbs***bsp;pad[tmp_n][tmp_m]=='G':
                    pad[tmp_n][tmp_m] = 'X' if pad[tmp_n][tmp_m]=='Y' else 'B'
                    tmp_n += 1
                    tmp_m += 1
                    if tmp_n==N&nbs***bsp;tmp_m==M: # 避免越界
                        break
            # /掉B
            tmp_n = n+1
            tmp_m = m-1
            if tmp_n==N&nbs***bsp;tmp_m==-1: # 避免越界
                pass
            else:
                while pad[tmp_n][tmp_m]=='B'&nbs***bsp;pad[tmp_n][tmp_m]=='G':
                    pad[tmp_n][tmp_m] = 'X' if pad[tmp_n][tmp_m]=='B' else 'Y'
                    tmp_n += 1
                    tmp_m -= 1
                    if tmp_n==N&nbs***bsp;tmp_m==-1: # 避免越界
                        break
            
        elif color=='Y': # \
            pad[n][m] = 'X'
            if m==M-1:   # 如果位于该行的最右边则轮到下一行
                continue
            tmp_n = n+1
            tmp_m = m+1
            if tmp_n==N&nbs***bsp;tmp_m==M: # 避免越界
                break
            while pad[tmp_n][tmp_m]=='Y'&nbs***bsp;pad[tmp_n][tmp_m]=='G':
                pad[tmp_n][tmp_m] = 'X' if pad[tmp_n][tmp_m]=='Y' else 'B'
                tmp_n += 1
                tmp_m += 1
                if tmp_n==N&nbs***bsp;tmp_m==M: # 避免越界
                    break
        elif color=='B': # /
            pad[n][m] = 'X'
            if m==0:     # 如果位于改行的第一个元素则轮到下一行
                continue
            tmp_n = n+1
            tmp_m = m-1
            if tmp_n==N&nbs***bsp;tmp_m==-1: # 避免越界
                break
            while pad[tmp_n][tmp_m]=='B'&nbs***bsp;pad[tmp_n][tmp_m]=='G':
                pad[tmp_n][tmp_m] = 'X' if pad[tmp_n][tmp_m]=='B' else 'Y'
                tmp_n += 1
                tmp_m -= 1
                if tmp_n==N&nbs***bsp;tmp_m==-1: # 避免越界
                    break
# 对最后一行进行捡漏
for color in pad[-1]:
    if color=='Y'&nbs***bsp;color=='B':
        res += 1
    elif color=='G':
        res += 2

#输出结果
print(res)

import sys
def Blue(i, j):
    l[i][j] = 'X'
    while i+1 <= n-1 and j-1 >= 0:
        if l[i+1][j-1] == 'B':
            l[i+1][j-1] = 'X'
        elif l[i+1][j-1] == 'G':
            l[i+1][j-1] = 'Y'
        else:
            return
        i += 1
        j -= 1
def Yellow(i, j):
    l[i][j] = 'X'
    while i+1 <= n-1 and j+1 <= m-1:
        if l[i+1][j+1] == 'Y':
            l[i+1][j+1] = 'X'
        elif l[i+1][j+1] == 'G':
            l[i+1][j+1] = 'B'
        else:
            return
        i += 1
        j += 1
while True:
    s1 = sys.stdin.readline().strip()
    if not s1:
        break
    n, m = map(int, s1.split(" "))
    l = []
    for i in range(n):
        l.append(list(sys.stdin.readline().strip()))
    count = 0
    for i in range(n):
        for j in range(m):
            if l[i][j] == 'B':
                Blue(i, j)
                count += 1
            elif l[i][j] == 'Y':
                Yellow(i, j)
                count += 1
            elif l[i][j] == 'G':
                Blue(i, j)
                Yellow(i, j)
                count += 2
    print(count)

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char c[55][55];

int main() {
    cin>>n>>m;
    for (int i = 1; i <=n ; ++i) {
        for (int j = 1; j <=m ; ++j) {
            cin>>c[i][j];
        }
    }
    //遍历 \ 方向
    for (int i = 1; i <= n + m - 1; ++i) {
        int s=0; //0表示没落笔的状态，1表示落笔
        for (int j = 1; j <= n; ++j) {
            int k = j + m - i;
            if (1 <= k && k <= m) {
                if (c[j][k] == 'Y' || c[j][k] == 'G') {
                    if(!s){
                        ans++;s++;
                    }
                }
                else if(s)s--;
            }
        }
    }
    //遍历 / 方向
    for (int i = 2; i <= n + m ; ++i) {
        int s = 0; //同上
        for (int j = 1; j <= n; ++j) {
            int k = i - j;
            if (1 <= k && k <= m) {
                if (c[j][k] == 'B' || c[j][k] == 'G') {
                    if(!s){
                        ans++;s++;
                    }
                }
                else if(s)s--;
            }
        }
    }
    cout<<ans;
}

90% 通过率？ 为什么啊

n,m = map(int, input().split(" "))
L = []
for i in range(n):
    L.append(list(input().strip()))
def change(L, coordinate, target):
    n, m = len(L), len(L[0])
    i, j = coordinate
    L[i][j] = target
    if target == 'B':
        # left_dowm
        count = 1
        for r in range(i, min(n, i + j + 1)):
            l = i + j - r
            if L[r][l] == 'B':
                L[r][l] = 'X'
            elif L[r][l] == 'G':
                L[r][l] = 'Y'
            else:
                break
    elif target == 'Y':
        # right_down
        count = 1
        for r in range(i, min(n, m + i - j)):
            l = r - i + j
            if L[r][l] == 'Y':
                L[r][l] = 'X'
            elif L[r][l] == 'G':
                L[r][l] = 'B'
            else:
                break
    else:
        change(L, coordinate, 'B')
        change(L, coordinate, 'Y')
        count = 2
    return count
def painter(L):
    n, m = len(L), len(L[0])
    for i in range(n):
        for j in range(m):
            target = L[i][j]
            if target != 'X':
                count = change(L, [i, j],target)
                return count + painter(L)
    else:return 0
print(painter(L))