首页 > 试题广场 >

画家小Q

[编程题]画家小Q
  • 热度指数:5276 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
画家小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最少需要多少次操作完成绘画。
示例1

输入

4 4
YXXB
XYGX
XBYY
BXXY

输出

3

说明

XXXX
XXXX
XXXX
XXXX
->
YXXX
XYXX
XXYX
XXXY
->
YXXB
XYBX
XBYX
BXXY
->
YXXB
XYGX
XBYY
BXXY
import java.util.*;
public class Main{
public static void main(String[]args){
Scanner scanner = new Scanner(System.in);
String tem = scanner.nextLine();
// 读入n的值
int n = Integer.valueOf(tem.split(" ")[0]);
// 读入m的值
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);
}
}
//求数组的行的最大下标
n=n-1;
//求数组的列的最大下标
m=m-1;
//调用求最小步数的方法
System.out.print(getMinStep(color,n,m));
}
//求最小步数的方法
public static int getMinStep(char [][]color,int n,int m){
//统计步数
int step=0;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
//如果值为绿色G 或者黄色Y 说明画的是“\” 是黄色,把黄色清除掉,并将步数加一
if(color[i][j]=='G'||color[i][j]=='Y'){
//调用清除黄色的方法 因为画的是“\”,所以要将 i+1,j+1
clearY(color,i+1,j+1,n,m);
//步数加一
step++;
}
//如果值为绿色G 或者蓝*** 说明画的是“/” 是B蓝色,把蓝色清除掉,并将步数加一
if(color[i][j]=='B'||color[i][j]=='G'){
//调用清除蓝色的方法,因为画的是“/”,所以要将 i-1,j+1
clearB(color,i+1,j-1,n,m);
//步数加一
step++;
}
continue;
}
}
return step;
}
//清除黄色Y的方法
public static void clearY(char [][]color,int i,int j,int n,int m){
//判断边界条件
while(n>=i&&m>=j){
//如果是绿色G,恢复到B蓝***r /> if(color[i][j]=='G'){
color[i][j]='B';
}
//如果是黄色Y,恢复到白色X
else if(color[i][j]=='Y'){
color[i][j]='X';
}
//如果是白色X,说明该斜线“\”断开了,后面的值不能修改,因为那是第二次画斜线的
//举例
/**
YXXX
XYXX
XXXX
XXXY
这算画了两次*/
else{
break;
}
i++;
j++;
}
}
//清除B蓝色的方法
public static void clearB(char [][]color,int i,int j,int n,int m){
//判断边界条件
while(n>=i&&j>=0){
//如果是绿色G,恢复到黄色Y
if(color[i][j]=='G'){
color[i][j]='Y';
}
//如果是蓝色G,恢复到白色X
else if(color[i][j]=='B'){
color[i][j]='X';
}
//如果是白色X,说明该斜线“/”断开了,后面的值不能修改,因为那是第二次画斜线的
//举例
/**
XXXB
XXXX
XBXX
BXXX
这算画了两次*/
else{
break;
}
i++;
j--;
}
}
}

编辑于 2019-09-05 22:58:47 回复(0)