実施-7.フライドチキン

質問する

サイズN×N人の町があります.都市は1×一つの大きさの格子に分ける.都市のどの部屋も空き部屋、フライドチキン屋、家の一つです.都市のセルは(r,c)と同じ形式で表示され、r行c列または上からr列、左からc列を表す.rとcは1から始まる.
この町に住んでいる人はチキンが大好きです.そのため、主に「チキンストリート」という言葉が使われています.フライドチキン街は家と一番近いフライドチキン屋の間の距離です.つまり、フライドチキン街は家を基準に定められており、どの家にもフライドチキン街があります.都市のフライドチキン街はすべての家のフライドチキン街の総和です.
任意の2つのセル(r 1,c 1)と(r 2,c 2)との間の距離を|r 1−r 2|+|c 1−c 2|で表す.
例えば、以下の地図がある都市を見てみましょう.

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

0は空いている1は家2はチキン屋
(2,1)上の家と(1,2)上のフライドチキン屋の距離は|2-1|+|1-2|=2,(5,5)上のフライドチキン屋の距離は|2-5|+|1-5|=7である.ということで、(2,1)家のチキンストリートは2.
(5,4)上の家と(1,2)上のフライドチキン屋の距離|5-1|+|4-2|=6、(5,5)上のフライドチキン屋の距離|5-5|+|4-5|=1.ということで、(5,4)家のチキンストリートは1.
この町のフライドチキン屋は同じチェーン店です.チェーン店本社は収益を上げるため、フライドチキン店の一部を閉鎖する計画だ.長い研究を経て、この都市で最もお金を稼ぐフライドチキン店はM社が最も多いことが分かった.
都市部のフライドチキン店ではM社が最も多く、残りのフライドチキン店は休業する.どのように選ぶか、都市のフライドチキン街が一番小さいかを求めるプログラムを作成してください.
入力

第1行はN(2≦N≦50)とM(1≦M≦13)を与える.

2行目からN行は都市の情報を与えている.
都市の情報は0,1,2で構成され,0はスペース,1は家,2はフライドチキン店である.家の数は2 Nを超えず、少なくとも1つ存在する.フライドチキン店の個数はM以上、13未満である.

しゅつりょく
1行目で最大M個の休業しないフライドチキン店を選ぶと、都市フライドチキン街の最高価格が出力されます.

入力例1

5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

出力例15

入力例2

5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2

出力例210

入力例3

5 1
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0

出力例311

入力例4

5 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1

出力例4

32

インプリメンテーションコード

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

class Node{
	private int x;
	private int y;
	public Node(int x, int y){
		this.x = x;
		this.y = y;
	}
	public int getX(){
		return this.x;
	}
	public int getY(){
		return this.y;
	}
}
public class Main{
	
	public static ArrayList<Node>house;
	public static ArrayList<Node>chicken;
	public static ArrayList<ArrayList<Node>>result;
	public static int m;
	public static boolean[] visited;
	
	public static void main(String args[])throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		house = new ArrayList<>();
		chicken = new ArrayList<>();
		for(int i = 0; i < n ; i++){
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < n; j++){
            	// 입력받은 값을 배열에 넣을 필요없이 1 이면 house Array에 2이면 chicken Array에 넣어준다.
				int k = Integer.parseInt(st.nextToken());
				if(k == 1){
					house.add(new Node(i ,j));
				}else if(k == 2){
					chicken.add(new Node(i ,j));
				}
			}
		}
        // 모든 조합을 넣어줄 Array (m 값에따라 선택 할 수있는 치킨집이 달라지므로)
		result = new ArrayList<ArrayList<Node>>();
        // 백트레킹 알고리즘 구현 시 치킨집 고름여부 
		visited = new boolean[chicken.size()];
		backtracking(0);
		
		
		int min = (int)1e9;
		for(int i = 0; i <result.size(); i++){
			ArrayList<Node> now = result.get(i);
			int sum2 = 0;
			for(int j = 0 ; j < house.size(); j++){
				int temp = (int)1e9;
				for(int k = 0; k < now.size(); k ++){
					temp = Math.min(temp,(Math.abs(house.get(j).getX() - now.get(k).getX())+ Math.abs(house.get(j).getY() - now.get(k).getY())));
				}
				sum2+= temp;
			}
			min =Math.min(min,sum2);
		}
		System.out.println(min);
	}
	
	public static void backtracking(int depth){
    	// 선택을 m개했을 시 선택한 값을 Arraylist 에 담아서 result 에 넣기.
		if(depth == m){
			ArrayList<Node>now = new ArrayList<>();
			for(int i = 0; i <chicken.size();i++ ){
				if(visited[i]){
					now.add(chicken.get(i));
				}
			}
			result.add(now);
			return;
		}
		for(int i = 0; i <chicken.size(); i ++){
			if(!visited[i]){
				visited[i] = true;
				backtracking(depth+1);
				visited[i] = false;
			}
		}
	}
}

コード解釈

この問題は後継問題と見てもよい.まず三重for文を使いましたが、もっと簡単な方法もあります.背もたれの場合は、最小値を比較して2重扉を使用できます.
並べ替え問題は近づきやすいと考えられていますが、計算中にエラーが発生しやすいです.