画家小Q
画家小Q又开始他的艺术创作。小Q拿出了一块有NxM像素格的画板, 画板初始状态是空白的,用’X’表示。
小Q有他独特的绘画技巧,每次小Q会选择一条斜线, 如果斜线的方向形如’/’,即斜率为1,小Q会选择这条斜线中的一段格子,都涂画为蓝色,用’B’表示;如果对角线的方向形如’’,即斜率为-1,小Q会选择这条斜线中的一段格子,都涂画为黄色,用’Y’表示。
如果一个格子既被蓝色涂画过又被黄色涂画过,那么这个格子就会变成绿色,用’G’表示。 小Q已经有想画出的作品的样子, 请你帮他计算一下他最少需要多少次操作完成这幅画。
简单翻译一下
意思就是你有一个 n * m 的画板，你可以在这个画板上画斜率为 1 的斜线，这条斜线上经过的格子填上Y。你也可以在这个画板上画斜率为 -1 的斜线，这条斜线上经过的格子填上B。如果同时被填上了B和Y，则这个格子变成G。
逆向思路
从左到右，从上到下遍历画板。在遍历时，遇到Y时，从当前格子往右下角的格子遍历。遇到Y，改成X。遇到G，改成B。遇到其他，则跳出当前往右下角的遍历。在遍历时，遇到B时，从当前格子往左下角的格子遍历。遇到B，改成X。遇到G，改成Y。遇到其他，则跳出当前往右下角的遍历。在遍历时，遇到G时，把G当成Y遍历一次。再把G当成B遍历一次。
上述思路是一种逆向的思维，是在还原画板。也可以是正向思维，重新定义一个新画板，在原画板上进行绘制。
附上逆向思路的代码
public static int calculation(int n
, int m
, char[][] origin
) {
int num
= 0;
for (int i
= 0; i
< n
; i
++){
for(int j
= 0; j
< m
; j
++){
if(origin
[i
][j
] == 'Y'){
handleY(n
,m
,i
,j
,origin
);
num
++;
} else if(origin
[i
][j
] == 'B'){
handleB(n
,m
,i
,j
,origin
);
num
++;
} else if(origin
[i
][j
] == 'G'){
handleG(n
,m
,i
,j
,origin
);
num
+= 2;
}
}
}
return num
;
}
public static void handleG(int n
,int m
,int i
,int j
,char[][] origin
) {
handleY(n
,m
,i
,j
,origin
);
handleB(n
,m
,i
,j
,origin
);
}
public static void handleY(int n
,int m
,int i
,int j
,char[][] origin
) {
while(i
< n
&& j
< m
){
if(origin
[i
][j
] == 'Y'){
origin
[i
][j
] = 'X';
} else if(origin
[i
][j
] == 'G'){
origin
[i
][j
] = 'B';
} else {
break;
}
i
++;
j
++;
}
}
public static void handleB(int n
,int m
,int i
,int j
,char[][] origin
){
while(i
<n
&& j
>= 0){
if(origin
[i
][j
] == 'B'){
origin
[i
][j
] = 'X';
} else if(origin
[i
][j
] == 'G'){
origin
[i
][j
] = 'Y';
} else {
break;
}
i
++;
j
--;
}
}
正向思路
定义一个大小相同，格子都是X的states画板。从左到右，从上到下遍历原有画板。在遍历原有画板时，遇到Y时，从当前格子往右下角的格子遍历。遇到Y或者G时，在states画板上写上Y。遇到其他，则跳出当前往右下角的遍历。在遍历原有画板时，遇到B时，从当前格子往右下角的格子遍历。遇到B或者G时，在states画板上写上B。遇到其他，则跳出当前往右下角的遍历。在遍历时，遇到G时，把G当成Y遍历一次。再把G当成B遍历一次。
附上正向思路的代码
public static int calculation1(int n
,int m
,char[][] origin
){
int num
= 0;
char[][] states
= new char[n
][m
];
for(int i
= 0; i
< n
; i
++){
for(int j
= 0; j
< m
; j
++){
states
[i
][j
] = 'X';
}
}
for(int i
= 0; i
< n
; i
++) {
for (int j
= 0; j
< m
; j
++) {
if(origin
[i
][j
] == 'Y'){
if(handleY1(i
,j
,n
,m
,origin
,states
)){
num
++;
}
} else if(origin
[i
][j
] == 'B'){
if(handleB1(i
,j
,n
,m
,origin
,states
)) {
num
++;
}
} else if(origin
[i
][j
] == 'G'){
if(handleY1(i
,j
,n
,m
,origin
,states
)){
num
++;
}
if(handleB1(i
,j
,n
,m
,origin
,states
)){
num
++;
}
}
}
}
return num
;
}
public static boolean handleB1(int i
,int j
,int n
,int m
,char[][] origin
,char[][] states
){
boolean isDraw
= false;
while(i
< n
&& j
>= 0){
if(states
[i
][j
] == 'B' || states
[i
][j
] == 'G'){
break;
}
if(origin
[i
][j
] == 'B' || origin
[i
][j
] == 'G'){
if(states
[i
][j
] == 'Y'){
states
[i
][j
] = 'G';
} else {
states
[i
][j
] = 'B';
}
isDraw
= true;
} else {
break;
}
i
++;
j
--;
}
return isDraw
;
}
public static boolean handleY1(int i
,int j
,int n
,int m
,char[][] origin
,char[][] states
){
boolean isDraw
= false;
while(i
< n
&& j
< m
){
if(states
[i
][j
] == 'Y' || states
[i
][j
] == 'G'){
break;
}
if(origin
[i
][j
] == 'Y' || origin
[i
][j
] == 'G'){
if(states
[i
][j
] == 'B'){
states
[i
][j
] = 'G';
} else {
states
[i
][j
] = 'Y';
}
isDraw
= true;
} else {
break;
}
i
++;
j
++;
}
return isDraw
;
}
