Ruudukko

public class Main {

	public static void main(String[] args) {
		IO io = new IO();

		int n = io.nextInt();
		
		char[] characters = new char[n * n];
		boolean[] possible = new boolean[n * n];
		possible[0] = true;
		for (int i = 0; i < n; i++) {
			char[] row = io.next().toCharArray();
			for (int j = 0; j < n; j++) {
				int index = j + i * n;
				characters[index] = row[j];
			}
		}
		
		String best = characters[0] + "";
		for (int i = 1; i < 2 * n - 1; i++) {
			int lowest = Integer.MAX_VALUE;
			for (int x = 0; x <= i; x++) {
				if(x >= n || i - x >= n) continue;
				int index = x + (i - x) * n;
				char left = ' ', up = ' ';
				if(x > 0) {
					if(possible[index-1])
					left = characters[index-1];
				}
				if(i - x > 0) {
					if(possible[index-n])
					up = characters[index-n];
				}
				char chr = characters[index];
				if(chr <= lowest && 
						( up == best.charAt(best.length()-1) || left == best.charAt(best.length()-1) ) ) {
					lowest = chr;
					possible[index] = true;
				}
				
			}
			best += (char)lowest;
		}
		
		io.println(best);
		
		io.close();
		
	}

}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED