[コケ]06-NMとK

NMとK

セルに整数を含むN行M列のグリッドでK個のセルを選択する問題.
選択したセルの数値和を最大化する問題
1<=N, M<=10, 1<=K<=min(4,N*M)

K個のセル->隣接できません.

再帰関数の使用

ex)100個から4個を選ぶ.100999897/4321

メソッドの数は多くなく、すべてのメソッドを作成できます.

cnt:選択したセルの数

sum:選択したセルの和

既存のセルに隣接することはできませんので、上、下、左、右の4方向の条件が必要です.

時間複雑度O(nm^k)

nとm(2)からstart~nへの概念を導入する.

選択したセルのローが常に昇順である場合は、重複を回避できます.

px:前の選択バーの行番号

ただし、同じ行で繰り返し選択できます.そこでpyを追加します.

(px,py):以前に選択したセル.

px == x , y=py+1

px>x, y=1

-nメソッドとmメソッドを直接使用します.

(r,c)は、r*M+cとして表すことができる.

~~私はあまり理解していませんが,,,,,,,,,,,,~~

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);
		}


}