CCC ’15 J4 – Wait Time

Canadian Computing Competition: 2018 Stage 1, Junior #4, Senior #2

Barbara plants  different sunflowers, each with a unique height, ordered from smallest to largest, and records their heights for  consecutive days. Each day, all of her flowers grow taller than they were the day before.

She records each of these measurements in a table, with one row for each plant, with the first row recording the shortest sunflower’s growth and the last row recording the tallest sunflower’s growth.

The leftmost column is the first measurement for each sunflower, and the rightmost column is the last measurement for each sunflower.

If a sunflower was smaller than another when initially planted, it remains smaller for every measurement.

Unfortunately, her children may have altered her measurements by rotating her table by a multiple of 90 degrees.

Your job is to help Barbara determine her original data.

Input Specification

The first line of input contains the number  . The next  lines each contain  positive integers, each of which is at most . It is guaranteed that the input grid represents a rotated version of Barbara’s grid.

Output Specification

Output Barbara’s original data, consisting of  lines, each of which contain  positive integers.

Sample Input 1

Copy

2
1 3
2 9

Sample Output 1

Copy

1 3
2 9

Explanation for Sample Output 1

The data has been rotated a multiple of 360 degrees, meaning that the input arrangement is the original arrangement.

Sample Input 2

Copy

3
4 3 1
6 5 2
9 7 3

Sample Output 2

Copy

1 2 3
3 5 7
4 6 9

Explanation for Sample Output 2

The original data was rotated 90 degrees to the right/clockwise.

Sample Input 3

Copy

3
3 7 9
2 5 6
1 3 4

Sample Output 3

Copy

1 2 3
3 5 7
4 6 9

Explanation for Sample Output 3

The original data was rotated 90 degrees to the left/counter-clockwise.

Solutions

import java.io.*;

public class C18J4Sunflower {
	private static int getTopLeft(String[][] grid, int N) {
		int[] cTopLeft = { 0, 0 }, cTopRight = { 0, N - 1 };
		int[] cBottomLeft = { N - 1, 0 }, cBottomRight = { N - 1, N - 1 };
		int[][] corners = { cTopLeft, cBottomLeft, cBottomRight, cTopRight };
		for (int i = 0; i < 4; i++) {
			int[] corner = corners[i];
			int cornerV = Integer.parseInt(grid[corner[0]][corner[1]]);
			switch (i) {
			case 0:
				if (cornerV < Integer.parseInt(grid[1][0]) && cornerV < Integer.parseInt(grid[0][1])) {
					return i;
				}
				break;
			case 1:
				if (cornerV < Integer.parseInt(grid[N - 2][0]) && cornerV < Integer.parseInt(grid[N - 1][1])) {
					return i;
				}
				break;
			case 2:
				if (cornerV < Integer.parseInt(grid[N - 2][N - 1]) && cornerV < Integer.parseInt(grid[N - 1][N - 2])) {
					return i;
				}
				break;
			case 3:
				if (cornerV < Integer.parseInt(grid[0][N - 2]) && cornerV < Integer.parseInt(grid[1][N - 1])) {
					return i;
				}
				break;
			}
		}
		return -1;
	}

	private static String[][] rotate(String[][] grid, int Z, int N) {
		String[][] newGrid;
		while (Z > 0) {
			newGrid = new String[N][N];
			for (int i = 0; i < N; i++) {
				String[] line = new String[N];
				for (int j = N - 1; j >= 0; j--) {
					line[N - 1 - j] = grid[j][i];
				}
				newGrid[i] = line;
			}
			grid = newGrid.clone();
			Z--;
		}
		return grid;
	}

	private static String[][] solve(String[][] grid, int N) {
		int corner = getTopLeft(grid, N);
		return rotate(grid, corner, N);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		String[][] grid = new String[N][N];
		for (int i = 0; i < N; i++) {
			String[] line = in.readLine().split(" ");
			grid[i] = line;
		}
		String[][] output = solve(grid, N);
		for (int i = 0; i < N; i++) {
			StringBuilder line = new StringBuilder();
			for (int j = 0; j < N; j++) {
				line.append(output[i][j] + " ");
			}
			System.out.println(line.toString());
		}
	}
}