• 재귀적으로 함수를 호출하면서 다음을 진행시킨다.
  • 한 칸 내려가는 곳이면 순회 방향과 동일하게 경사로를 놓을 수 있는지 확인할 수 있지만, 한 칸 올라가는 곳이면 순회 방향의 역순으로 경사로를 놓을 수 있는지 확인해야 하기 때문에 방문 여부가 필요하다
  • dfs1()은 col이 증가하는 방향으로 진행하고, dfs2()는 row가 증가하는 방향으로 진행한다.
  • 각 row별로 dfs1()을 호출하고 각 col별로 dfs2()를 호출하기 전에 방문 여부 배열을 초기화한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87



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

public class Main {
	static int N, X;
	static int[][] board;
	static boolean[][] visited;

	static boolean dfs1(int r, int c) {
		if (c >= N-1) return true;

		int nc = c + 1;
		if (board[r][c] == board[r][nc])
			return dfs1(r, nc);
		else if (board[r][c] == board[r][nc] + 1) { // down
			int comparison = board[r][nc];
			for (int nnc = nc; nnc < nc + X; nnc++) {
				if \(nnc >= N \|| board\[r]\[nnc] != comparison \|| visited\[r]\[nnc])
					return false;
				visited[r][nnc] = true;
			}
			return dfs1(r, c + X);
		} else if (board[r][c] + 1 == board[r][nc]) { // up
			int comparison = board[r][c];
			for (int nnc = c; nnc > c - X; nnc--) {
				if \(nnc < 0 \|| board\[r]\[nnc] != comparison \|| visited\[r]\[nnc])
					return false;
				visited[r][nnc] = true;
			}
			return dfs1(r, c + 1);
		} else return false; // 차이 2 이상 
	}

	static boolean dfs2(int r, int c) {
		if (r >= N-1) return true;

		int nr = r + 1;
		if (board[r][c] == board[nr][c])
			return dfs2(nr, c);
		else if (board[r][c] == board[nr][c] + 1) { // down
			int comparison = board[nr][c];
			for (int nnr = nr; nnr < nr + X; nnr++) {
				if \(nnr >= N \|| board\[nnr]\[c] != comparison \|| visited\[nnr]\[c])
					return false;
				visited[nnr][c] = true;
			}
			return dfs2(r + X, c);
		} else if (board[r][c] + 1 == board[nr][c]) { // up
			int comparison = board[r][c];
			for (int nnr = r; nnr > r - X; nnr--) {
				if \(nnr < 0 \|| board\[nnr]\[c] != comparison \|| visited\[nnr]\[c])
					return false;
				visited[nnr][c] = true;
			}
			return dfs2(r + 1, c);
		} else return false; // 차이 2 이상
	}

	static int solution() {
		int cnt = 0;
		for (int r = 0; r < N; r++)
			cnt += dfs1(r, 0) ? 1 : 0;

		for (int i = 0; i < N; i++)
			Arrays.fill(visited[i], false);

		for (int c = 0; c < N; c++)
			cnt += dfs2(0, c) ? 1 : 0;

		return cnt;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken());
		board = new int[N][N];
		visited = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++)
				board[i][j] = Integer.parseInt(st.nextToken());
		}
		System.out.println(solution());
	}
}