17406. 배열 돌리기 4

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

public class B_17406_배열돌리기4 {

	static boolean[] check;
	static int N, M, K;
	static int[][] circle, arr;
	static int Min = Integer.MAX_VALUE;
	static int[] rotate;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		check = new boolean[K];
		rotate = new int[K];
		// 배열 생성 및 할당
		arr = new int[N + 1][M + 1];
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 1; j <= M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// 회전의 연산 입력 받기
		circle = new int[K][3];
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			circle[i][0] = Integer.parseInt(st.nextToken());
			circle[i][1] = Integer.parseInt(st.nextToken());
			circle[i][2] = Integer.parseInt(st.nextToken());
		}

		permutation(0);
		System.out.println(sb.append(Min));
	}

	private static void permutation(int cnt) { // 함수로 순열돌리고
		if (cnt == K) {
			int[][] map = new int[N + 1][M + 1]; // 배열 복사
			for (int i = 0; i <= N; i++) {
				for (int j = 0; j <= M; j++) {
					map[i][j] = arr[i][j];
				}
			}
			solve(map, rotate);
		}
		for (int i = 0; i < K; i++) {
			if (check[i] == false) {
				check[i] = true;
				rotate[cnt] = i; // rotate 배열은 전역으로
				permutation(cnt + 1);
				check[i] = false;
			}
		}
	}

	private static void solve(int[][] map, int[] rotate) {
		for (int i = 0; i < K; i++) {
			int[] start = { circle[rotate[i]][0] - circle[rotate[i]][2], circle[rotate[i]][1] - circle[rotate[i]][2] };
			int[] end = { circle[rotate[i]][0] + circle[rotate[i]][2], circle[rotate[i]][1] + circle[rotate[i]][2] };
			int width = end[1] - start[1] + 1;
			int height = end[0] - start[0] + 1;
			int circleNum = Math.min(width, height) / 2;

			for (int c = 0; c < circleNum; c++) { // 회전 원의 개수만큼(바깥 -> 안)
				// 회전의 기준점 - 좌측상위, 우측하위
				int sy = start[0] + c;
				int sx = start[1] + c;
				int ey = end[0] - c;
				int ex = end[1] - c;
				int tmp = map[sy][sx];

				// 왼쪽 줄을 위로 올리기
				for (int j = 1; sy + j <= ey; j++) {
					map[sy + j - 1][sx] = map[sy + j][sx];
				}
				// 아래줄 왼쪽으로
				for (int j = 1; sx + j <= ex; j++) {
					map[ey][sx + j - 1] = map[ey][sx + j];
				}
				// 오른쪽 줄 아래로
				for (int j = 1; ey - j >= sy; j++) {
					map[ey - j + 1][ex] = map[ey - j][ex];
				}
				// 위줄 오른쪽으로
				for (int j = 1; ex - j > sx; j++) {
					map[sy][ex - j + 1] = map[sy][ex - j];
				}
				map[sy][sx + 1] = tmp;
			}
		}
		minCalcurator(map);
	}

	private static void minCalcurator(int[][] map) { // 배열 각 계산 후 최솟값 도출
		int min = Integer.MAX_VALUE;
		for (int i = 1; i <= N; i++) {
			int sum = 0;
			for (int j = 1; j <= M; j++) {
				sum += map[i][j];
			}
			min = Math.min(min, sum);
		}
		Min = Math.min(Min, min);
	}
}