这是白峻1018号。

碁盤を塗り直す

質問する

志敏は自分の住宅で、MN単位の正方形で区切られたM.×Nサイズのボードが見つかりました.一部の正方形は黒に塗り、残りは白に塗ります.志敏はこの板を8切った.×8ヤードのチェス盤を作ります.
チェスの碁盤は白黒の間にあるべきだ.具体的には、各セルは白黒の1つに塗り、共有エッジの2つの長方形は異なる色に塗ります.したがって,この定義によれば,チェス盤が色付く場合は2つしかない.一つは左上の格子が白で、一つは黒です.
スケートボードがチェス盤のように塗る保証がないので、智敏8×8ヤードのチェス盤に切って、正方形をいくつか塗りたいです.もちろん8*8の大きさは自由に選べます.プログラムを書いて、志敏が塗り直す正方形の最小個数を求めます.

入力

1行目はNとMです.NとMは8以上、50以下の自然数である.2行目からN行目まで、板上の各行の状態が与えられる.Bは黒、Wは白です.

しゅつりょく

最初の行は、志敏が塗り直す正方形の個数の最大値を出力します.

例

コード#コード#

import java.util.*;
import java.io.*;

public class Main {
	 
	public static boolean[][] arr;
	public static int min = 64;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
 
		arr = new boolean[M][N];
		
		for (int i=0; i<M; i++) {
			String str = br.readLine();
			
			for (int j=0; j<N; j++) {
				if (str.charAt(j) == 'W') 
					arr[i][j] = true;		
				else 
					arr[i][j] = false;			
			}
		}

		int M_row = M - 7;
		int N_col = N - 7;
 
		for (int i=0; i<M_row; i++) {
			for (int j=0; j<N_col; j++) 
				find(i, j);
		}
		System.out.println(min);
	}
 
	public static void find(int x, int y) {
		int end_x = x + 8;
		int end_y = y + 8;
		int count = 0;
 
		boolean TF = arr[x][y];	
 
		for (int i = x; i < end_x; i++) {
			for (int j = y; j < end_y; j++) {
				if (arr[i][j] != TF)	
					count++;
				
				TF = (!TF);
			}
			TF = !TF;
		}
	
		count = Math.min(count, 64 - count);
		min = Math.min(min, count);
	}
}

に答える

解くのは難しい...
他のネットの達人をたくさん参考にしました.
白をTrue,黒をFalseとするboolean型配列と変数を用いた.
一度に白が現れると、右側に反対の色が現れるはずです.また、次の行の最初のタイルの色は黒でなければなりません.この論理を思いついた.
また、1列目のタイルは白い板で、黒い板は2種類あります.
そのため、2 × (가로 칸 개수 - 7) × (세로 칸 개수 - 7).