4014. [모의 SW 역량테스트] 활주로 건설

Solution.java

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

public class Solution {
	
	public static boolean isInBound(int[] row, int from, int to) {
		if (from < 0 || to >= row.length) {
			return false;
		}
		return true;
	}
	
	public static boolean isFlat(int[] row, int from, int to) {
		int height = row[from];
		for (int i = from; i <= to; ++i) {
			if (row[i] != height) {
				return false;
			}
		}
		return true;
	}
	
	public static boolean isOccupied(boolean[] built, int from, int to) {
		for (int i = from; i <= to; ++i) {
			if (built[i]) { return true; }
		}
		return false;
	}
	
	public static void constructBuilding(boolean[] built, int from, int to) {
		for (int i = from; i <= to; ++i) {
			built[i] = true;
		}
	}
	
	public static boolean go(int[] row, int i, int sizeBuilding, boolean[] built) {
		if (i >= row.length - 1) { // 0. traveled all the way / reaching the end (terminate condition)
			return true; // && 1
		}
		if (row[i] == row[i + 1]) { // 1. flat
			return go(row, i + 1, sizeBuilding, built);
		} else if (row[i] - 1 == row[i + 1]) { // 2. going down
			int from = i + 1;
			int to = i + sizeBuilding;
			if (isInBound(row, from, to) 
					&& isFlat(row, from, to) 
					&& !isOccupied(built, from, to)) {
				constructBuilding(built, from, to);
				return go(row, i + sizeBuilding - 1, sizeBuilding, built);
			} else {
				return false;
			}
		} else if (row[i] + 1 == row[i + 1]) { // 3. going up
			int from = i - sizeBuilding + 1;
			int to = i;
			if (isInBound(row, from, to) 
					&& isFlat(row, from, to) 
					&& !isOccupied(built, from, to)) {
				constructBuilding(built, from, to);
				return go(row, i + 1, sizeBuilding, built);
			} else {
				return false;
			}
		} else { // 4. bad cliff
			return false;
		}
	}

	public static void main(String args[]) throws Exception {
		final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		final int nTestCases = Integer.parseInt(br.readLine()); // !
		final StringBuilder ret = new StringBuilder();
		
		for (int testCase = 0; testCase < nTestCases; ++testCase) {
			final StringTokenizer st1 = new StringTokenizer(br.readLine());
			
			final int sizeTerrain = Integer.parseInt(st1.nextToken()); // !
			final int sizeBuilding = Integer.parseInt(st1.nextToken()); // !
			final int[][] terrain = new int[sizeTerrain][sizeTerrain]; // !
			
			for (int row = 0; row < sizeTerrain; ++row) {
				final StringTokenizer st2 = new StringTokenizer(br.readLine());
				for (int col = 0; col < sizeTerrain; ++col) {
					terrain[row][col] = Integer.parseInt(st2.nextToken());
				}
			} // int[][] terrain
			
			int answer = 0;

			for (int row = 0; row < sizeTerrain; ++row) {
				answer += go(terrain[row], 0, sizeBuilding, new boolean[sizeTerrain])?1:0;
			}
			
			for (int col = 0; col < sizeTerrain; ++col) {
				int[] arr = new int[sizeTerrain];
				for (int row = 0; row < sizeTerrain; ++row) {
					arr[row] = terrain[row][col];
				}
				answer += go(arr, 0, sizeBuilding, new boolean[sizeTerrain])?1:0;
			}
			
			ret.append('#');
			ret.append(testCase + 1);
			ret.append(' ');
			ret.append(answer);
			ret.append('\n');
		} // for testcase
		
		System.out.println(ret);
		
	} // main()
	
} // public class