[伯俊](Java)15655-NとM(6)

14938 ワード
DFS Java 白駿 テキストリンク
質問リンク
https://www.acmicpc.net/problem/15655
問題を解く
dfsスケルトン問題には重複する数値の組み合わせがあるべきではない.
ex)17が現れると7 1は(x)
n,mの範囲は大きくない
idx=mの場合
chkの要素をStringに接続する
Mapのキーで作ります.
ex)1 2 3 4のうち1 3のキーがtrueFalsetrueFalseになります.
3 1のキー値もtrueFalseTrueFalseになりますので、同じキー値を順番に作成できます.
            String key = "";
            for(int i=0; i<chk.length; i++){
                key+=chk[i]+"";
            }
mapに対応するキーがない場合は、対応する結果値が出力されます.
mapにキー値を入力し、同じ数字の組み合わせを出力しないようにします.
if(!chkmap.containsKey(key)){
                for (int i = 0; i < m; i++) {
                    System.out.print(list[i] + " ");
                }
                System.out.println("");
                chkmap.put(key,0);
                return;
            }
コード#コード#
import java.util.*;


public class Main {

    static int n;
    static int m;
    static int[] arr;
    static boolean[] chk;
    static int[] list;
    static Map<String, Integer> chkmap = new HashMap<>();

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n];
        chk = new boolean[n];
        list = new int[m];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        dfs(0);
    }

    public static void dfs(int idx) {

        if (idx == m) {
            String key = "";
            for(int i=0; i<chk.length; i++){
                key+=chk[i]+"";
            }

            if(!chkmap.containsKey(key)){
                for (int i = 0; i < m; i++) {
                    System.out.print(list[i] + " ");
                }
                System.out.println("");
                chkmap.put(key,0);
                return;
            }
            return;
        }


        for (int i = 0; i < n; i++) {
            if (chk[i]) {
                continue;
            }
            list[idx] = arr[i];
            chk[i] = true;
            dfs(idx + 1);
            chk[i] = false;
        }
    }
}
Android携帯電話内蔵SDカードパスの取得
寸法リソースの使用