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 > 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;
}
}
在这段代码中,if(count == 0) i = a[x] 的作用是确保第一个位置上的手指值与输入数组中对应位置的值相匹配。如果我们去掉这段代码,那么第一个位置上的手指值将会根据循环中的变量 i 迭代取值,而不是根据输入数组确定。
假设输入数组 a = {3, 1, 2, 4, 5},如果我们去掉 if(count == 0) i = a[x] 这段代码,那么程序将会按照以下步骤执行:
而如果我们保留 if(count == 0) i = a[x] 这段代码,将根据输入数组确定第一个位置上的手指值为 3。这样,在递归调用 dfs 函数处理下一个位置时,就不会再出现第一个位置上的手指值为 1 的情况。
这段代码中的 if(count == 0) i = a[x]
只在初始情况下执行一次,目的是将第一个位置上的手指值与输入数组中对应位置的值相匹配。
在回溯算法中,我们通常使用一个计数器(例如 count
)来追踪当前处理的手指位置。当 count
的值为 0 时,说明我们正在处理第一个位置上的手指值,此时我们通过 if(count == 0) i = a[x]
将第一个位置上的手指值设定为输入数组中对应位置的值。
在后续的递归调用中,count
的值将不再为 0,因此这段代码将不会再执行,保持当前处理的手指值不变。这样可以确保程序按照正确的顺序生成所有可能的手指排列。
所以,即使 count
只有在初始时为 0,这段代码仍然是必要的,它确保了第一个位置上的手指值正确地与输入数组匹配。
原文地址:https://blog.csdn.net/screamn/article/details/134675845
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_4617.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!