3536970_wa.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {
	private Scanner in;
	private int w, h;
	private int [][] panel;
	private int index;
	private Info [] info = new Info [100];
	private int [][] cnt;
	private boolean [][] is;

	class Info {
		int x, y;
		int length;

		public Info(int x, int y, int length) {
			this.x = x;
			this.y = y;
			this.length = length;
		}

		private void mark() {
			for (int i = x; i < x + length; i++) {
				for (int j = y; j < y + length; j++) {
					is[i][j] = true;
				}
			}
		}

		public int check() {
			for (int i = x; i < x + length; i++) {
				for (int j = y; j < y + length; j++) {
					if (cnt[i][j] == 1) {
						mark();
						return 0;
					}
				}
			}
			for (int i = x; i < x + length; i++) {
				for (int j = y; j < y + length; j++) {
					if (!is[i][j]) {
						cnt[i][j]--;
					}
				}
			}
			return 1;
		}
	}

	public static void main(String [] args) {
		new Main().run();
	}

	private void run() {
		in = new Scanner(System.in);

		while (true) {
			w = in.nextInt();
			h = in.nextInt();
			if (w == 0 && h == 0) {
				break;
			}
			panel = new int [h][w];
			cnt = new int [h][w];
			is = new boolean [h][w];
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					panel[i][j] = in.nextInt();
				}
			}
			index = 0;
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (panel[i][j] == 1) {
						boolean isnew = false, tmpnew = false;
						int l, x, y;
						
				loop1:	for (l = 1, x = i; x < h; x++, l++) {
							for (y = j; y < j + l; y++) {
								if (y >= w || panel[x][y] != 1) {
									break loop1;
								}
								tmpnew = (cnt[x][y] == 0);
							}
							for (y = i; y < i + l; y++) {
								if (y >= h || panel[y][j+l-1] != 1) {
									break loop1;
								}
								tmpnew = (cnt[y][j+l-1] == 0);
							}
							isnew = tmpnew;
						}
						l--;
						if (isnew) {
							//System.out.println("l is " + l);
							for (x = i; x < i + l; x++) {
								for (y = j; y < j + l; y++) {
									cnt[x][y]++;
								}
							}
							info[index++] = new Info(i, j, l);
						}
					}
				}
			}
			int ans = index;
			for (int i = 0; i < index; i++) {
				int tmp;
				ans -= (tmp = info[i].check());
				//if (tmp == 1) {
				//	System.out.println("x " + info[i].x + " y " + info[i].y + " len " + info[i].length);
				//}
			}
			System.out.println(ans);
		}
	}
}