洛谷火柴人_代码007

本文介绍: 在这段代码中，if(count == 0) i = a[x] 的作用是确保第一个位置上的手指值与输入数组中对应位置的值相匹配。如果我们去掉这段代码，那么第一个位置上的手指值将会根据循环中的变量 i 迭代取值，而不是根据输入数组确定。这样，在递归调用 dfs 函数处理下一个位置时，就不会再出现第一个位置上的手指值为 1 的情况。只有在初始时为 0，这段代码仍然是必要的，它确保了第一个位置上的手指值正确地与输入数组匹配。只在初始情况下执行一次，目的是将第一个位置上的手指值与输入数组中对应位置的值相匹配。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
    static int n;
    static int number = 0;
    static int[] arr = new int[20000];
    static boolean[] st = new boolean[20000];
    static int s;
    static int count = 0;
    static boolean judge = true;
    static boolean return0 = false;
    static int[] a = new int[20000];

    public static void main(String[] args) throws Exception {
        Read sc = new Read();
        n = sc.nextInt();
        s = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        dfs(1);
    }

    public static int dfs(int x) {
        if (return0) {
            return 0;
        }
        if (x &gt; n) {
            count++;
            for (int i = 1; i <= n; i++) {
                if (a[i] != arr[i])
                    judge = false;
            }
            if (judge) {
                number = count;
                judge = false;
            }
            if (count == s + number) {
                return0 = true;
                for (int i = 1; i <= n; i++) {
                    System.out.print(arr[i] + " ");
                }
                System.out.println();
                return 0;
            }
            return 0;
        }
        for (int i = 1; i <= n; i++) {
            if (count == 0) {
                i = a[x];
            }
            if (!st[i]) {
                st[i] = true;
                arr[x] = i;
                dfs(x + 1);
                st[i] = false;
                arr[x] = 0;
            }

        }
        return 0;
    }
}

class Read {
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public int nextInt() throws Exception {
        st.nextToken();
        return (int) st.nval;
    }

    public long nextLong() throws Exception {
        st.nextToken();
        return (long) st.nval;
    }
}