카드뒤집기

07월 08일 in Category / Algorithm

카드 뒤집기

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution_gyu_카드뒤집기 {
	static int T, N, MAX;
	static int map[][];
	static int count[][];
	static int dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/Solution_gyu_카드뒤집기.txt"));
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(in.readLine().trim());

		for (int test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(in.readLine().trim());
			map = new int[N+2][N+2];
			count = new int[N+2][N+2];

			for(int i=1; i<=N; i++) {
				st = new StringTokenizer(in.readLine());
				for(int j=1; j<=N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			MAX = -1;

			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					if(map[i][j]!=0 && count[i][j]==0) {
						gameStart(i, j);
						MAX = Math.max(MAX, count[i][j]);
					}
				}
			}
			System.out.println("#"+test_case+" "+MAX);
		}
	}

	private static void gameStart(int r, int c) {
		int dr, dc;

		for (int i = 0; i < 4; i++) {
			dr = r + dir[i][0];
			dc = c + dir[i][1];
			if (map[dr][dc] != 0 && map[dr][dc] > map[r][c]) {
				count[dr][dc] = 1;
				gameStart(dr, dc);
				count[r][c] = Math.max(count[r][c], count[dr][dc] + 1);
			}
		}
	}

}