[コケ]06-NMとK

NMとK

import java.util.Scanner;

public class Main {
		static int a[][] = new int[10][10];
		static boolean c[][]= new boolean[10][10];
		static int n,m,k;
		static int max = -999999999;
		static int dx[] = {0,0,1,-1};
		static int dy[] = {1,-1,0,0};
		
		static void go(int px, int cnt, int sum) {
			if(cnt==k) {	//선택한 칸의 개수가 k와 같다면 max에 최대값을 넣어줌.
				if(max < sum) max = sum;
				return;
			}
			
			//px는 이전에 선택한 칸의 행 번호. 그 번호부터 n까지 for문
			for(int x=px; x<n;x++) {
				for(int y=0;y<m;y++) {
					if(c[x][y])
						continue;
					boolean ok = true;
					for(int i=0;i<4;i++) {
						int nx = x+dx[i];
						int ny = y+dy[i];
						
						//인접한 4가지 방향 조건, 인접했으면 false
						if(0 <= nx && nx < n && 0 <=ny && ny < m)
							if(c[nx][ny]) ok = false;
					}
				//인접하지 않았을 경우 true. 
				if(ok) {
					c[x][y] =true;
					go(x, cnt+1, sum+a[x][y]);
					//x는 현재의 칸의 행번호이지만 재귀함수로 넘어가게 되면 이전의 칸의 행번호가 됨.
					
					c[x][y] = false;	//함수의 호출을 미리 준비하는 것. false로 주고,,
				}
				}
			}
		}

		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			n = sc.nextInt();
			m = sc.nextInt();
			k = sc.nextInt();
			
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					a[i][j]= sc.nextInt();	//격자판에 들어있는 숫자 입력
				}
			}
			
			go(0,0,0);
			System.out.println(max);
		}


}