Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-30SRM300台を練習していく part6

SRM 311 MatrixTransforming

|  SRM 311 MatrixTransforming - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 311 MatrixTransforming - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6431

3x3のマスをflipする操作を繰り返す。最小何回で目的のパターンが作れるか?

左上のマスが合っていなければflipする という操作を全てのマスで試せばおk


public class MatrixTransforming {

	public int minPushes(String[] a, String[] b) {
		int w = a[0].length();
		int h = a.length;
		int[] dx = {0, 1, 2, 0, 1, 2, 0, 1, 2};
		int[] dy = {0, 0, 0, 1, 1, 1, 2, 2, 2};

		int[][] aa = new int[h][w];
		int[][] bb = new int[h][w];
		for (int y = 0 ; y < h ; y++) {
			for (int x = 0 ; x < w ; x++) {
				aa[y][x] = a[y].charAt(x) - '0';
				bb[y][x] = b[y].charAt(x) - '0';
			}
		}

		int flips = 0;
		for (int y = 0 ; y <= h - 3 ; y++) {
			for (int x = 0 ; x <= w - 3 ; x++) {
				if (aa[y][x] != bb[y][x]) {
					for (int d = 0 ; d < 9 ; d++) {
						aa[y+dy[d]][x+dx[d]] = 1 - aa[y+dy[d]][x+dx[d]];
					}
					flips++;
				}
			}
		}


		for (int y = 0 ; y < h ; y++) {
			for (int x = 0 ; x < w ; x++) {
				if (aa[y][x] != bb[y][x]) {
					return -1;
				}
			}
		}

		return flips;
	}

}