UVA-11212 编辑书稿 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

这道题目在书上的“迭代加深搜索”章节出现，即是采用迭代加深搜索的方法来做。

但是咋一看题目，我认为用广度优先搜索也合适。因为题目要求是找到最短的粘贴次数，使用程序遍历一层一层搜搜正合适。而且数据量也不算太大， 队列和是否访问过的flag都可以存下。

如果使用迭代加深搜索，搜到第n+1次时，会对前n次的计算结果进行重复搜索，效率不高。但是层序遍历则没这个问题。

有些同学会说迭代加深搜索可以剪枝，可以有启发函数。那么广度优先搜索也可以剪枝，也可以有启发函数，而且是一样的启发函数。因此这不是问题。

由于需要练习“迭代加深搜索”，因此我还是用这个方法做的，感兴趣的同学可以试一下广度优先搜索是否合适。

我尝试使用了flag记录使用访问过的标志，但是发现这样效率更低。如果剪枝合适，不记录也是可以的。

使用flag记录： 7270ms

不使用flag记录： 1400ms

数据粘贴的还原的方法我做的比较繁琐，但是比较容易理解，这个还可以优化。

使用flag记录的代码（更慢）

#include<stdio.h>
#include<string.h>

int n;
int origin[10];
int arrnow[10];
int arrtemp[10];
char findMap[1000000000];

void printArr(int * arr) {
	for(int i = 0; i < n; ++i) {
		printf("%d ", arr[i]);
	}
	printf("\n");
} 

// 是否访问过

bool isFind(int * arr, int step) {
	int num = 0;
	for(int i = 0; i < n; ++i) {
		num = num * 10 + arr[i]-1;
	}
	if(!findMap[num]) return false;
	return findMap[num] < step;
}

// 设置访问 
void findFlag(int * arr, int step) {
	int num = 0;
	for(int i = 0; i < n; ++i) {
		num = num * 10 + arr[i]-1; 
	}
	findMap[num] = step; 
}

// 获取数组中后继不正确的数字个数 
int getErrorNum(int * arr) {
	int num = 0;
	for(int i = 1; i < n; ++i) {
		if(arr[i] != arr[i-1]+1) ++num;
	}
	return num;
} 

// 当前最少需要的移动次数 
int getMinTime(int * arr) {
	int num = getErrorNum(arr);
	if(num % 3) return num / 3 + 1;
	return num / 3;
}

// 移动位置 
void movePos(int start, int end, int pos) {
	memcpy(arrtemp, arrnow, sizeof(arrnow));
	int movelen = end-start + 1;
	int i, j, k;
	if(start > pos) {
		for(i = 0; i < movelen; ++i)
		arrnow[pos + i] = arrtemp[start + i];
		for(i = 0; i < pos; ++i)
			arrnow[i] = arrtemp[i];
		for(i = pos; i < start; ++i)
			arrnow[i + movelen] = arrtemp[i];
		for(i = end+1; i < n; ++i)
			arrnow[i] = arrtemp[i];
	}
	if(end < pos) {
		for(i = 0; i < movelen; ++i)
			arrnow[pos + i - movelen] = arrtemp[start + i];
		for(i = 0; i < start; ++i)
			arrnow[i] = arrtemp[i];
		for(i = end+1; i < pos; ++i)
			arrnow[i-movelen] = arrtemp[i];
		for(i = pos; i < n; ++i)
			arrnow[i] = arrtemp[i];
	}
}

// 恢复之前移动的位置 
void restorePos(int start, int end, int pos) {
	int movelen = end-start + 1;
	if(start > pos)
		movePos(pos, pos + movelen - 1, start + movelen);
	if(end < pos)
		movePos(pos - movelen, pos-1, start);
}

// 每一轮迭代
bool handleTime(int num, int len) {
	// printf("%d %d\n",num, getErrorNum(arrnow));
	// 到达终点 
	if(num == len) {
		if(!getErrorNum(arrnow)) return true;
		return false;
	}
	// 继续迭代 
	int i, j, k, numnow;
	for(int i = 0; i < n; ++i) {
		if(i != 0 && arrnow[i-1] == arrnow[i]-1) continue;
		for(j = i; j < n; ++j) {
			if(j != n-1 && arrnow[j+1] == arrnow[j]+1) continue;
			for(k = 0; k <= n; ++k) {
				if(k >= i-1 && k <= j+1) continue;
				// printf("-------\n");
				// printArr(arrnow);
				// 移动
				movePos(i, j, k);
				numnow = num + 1;
				// printf("%d %d %d\n", i, j, k);
				// printArr(arrnow);
				// 剪枝
				if((getMinTime(arrnow) <= (len - numnow)) && !isFind(arrnow, numnow)) {
				// if(getMinTime(arrnow) <= (len - num)) {
					findFlag(arrnow, numnow);
					// 递归
					if(handleTime(numnow, len)) return true;
				}
				// 恢复
				restorePos(i, j, k);
				// printArr(arrnow);
			}
		}
	}
	return false;
}

// 处理入口 
int handle() {
	int i, j;
	for(i = getMinTime(origin); i < 8; ++i) {
		memcpy(arrnow, origin, sizeof(arrnow));
		memset(findMap, 0, sizeof(findMap));
		// 每一轮加深迭代
		if(handleTime(0, i)) return i;
	}
	return 8; 
}

int main() {
	int t = 0;
	int i, j;
	while(scanf("%d\n", &n) == 1 && n > 0) {
		++t;
		for(i = 0; i < n; ++i)
			scanf("%d", &origin[i]);
		j = handle();
		printf("Case %d: %d\n", t, j);
	}
	return 0;	
}

不使用flag记录的代码

#include<stdio.h>
#include<string.h>

int n;
int origin[10];
int arrnow[10];
int arrtemp[10];

void printArr(int * arr) {
	for(int i = 0; i < n; ++i) {
		printf("%d ", arr[i]);
	}
	printf("\n");
} 

// 获取数组中后继不正确的数字个数 
int getErrorNum(int * arr) {
	int num = 0;
	for(int i = 1; i < n; ++i) {
		if(arr[i] != arr[i-1]+1) ++num;
	}
	return num;
} 

// 当前最少需要的移动次数 
int getMinTime(int * arr) {
	int num = getErrorNum(arr);
	if(num % 3) return num / 3 + 1;
	return num / 3;
}

// 移动位置 
void movePos(int start, int end, int pos) {
	memcpy(arrtemp, arrnow, sizeof(arrnow));
	int movelen = end-start + 1;
	int i, j, k;
	if(start > pos) {
		for(i = 0; i < movelen; ++i)
		arrnow[pos + i] = arrtemp[start + i];
		for(i = 0; i < pos; ++i)
			arrnow[i] = arrtemp[i];
		for(i = pos; i < start; ++i)
			arrnow[i + movelen] = arrtemp[i];
		for(i = end+1; i < n; ++i)
			arrnow[i] = arrtemp[i];
	}
	if(end < pos) {
		for(i = 0; i < movelen; ++i)
			arrnow[pos + i - movelen] = arrtemp[start + i];
		for(i = 0; i < start; ++i)
			arrnow[i] = arrtemp[i];
		for(i = end+1; i < pos; ++i)
			arrnow[i-movelen] = arrtemp[i];
		for(i = pos; i < n; ++i)
			arrnow[i] = arrtemp[i];
	}
}

// 恢复之前移动的位置 
void restorePos(int start, int end, int pos) {
	int movelen = end-start + 1;
	if(start > pos)
		movePos(pos, pos + movelen - 1, start + movelen);
	if(end < pos)
		movePos(pos - movelen, pos-1, start);
}

// 每一轮迭代
bool handleTime(int num, int len) {
	// 到达终点 
	if(num == len) {
		if(!getErrorNum(arrnow)) return true;
		return false;
	}
	// 继续迭代 
	int i, j, k, numnow;
	for(int i = 0; i < n; ++i) {
		if(i != 0 && arrnow[i-1] == arrnow[i]-1) continue;
		for(j = i; j < n; ++j) {
			if(j != n-1 && arrnow[j+1] == arrnow[j]+1) continue;
			for(k = 0; k <= n; ++k) {
				if(k >= i-1 && k <= j+1) continue;
				// 移动
				movePos(i, j, k);
				numnow = num + 1;
				// 剪枝
				if((getMinTime(arrnow) <= (len - numnow))) {
					// 递归
					if(handleTime(numnow, len)) return true;
				}
				// 恢复
				restorePos(i, j, k);
			}
		}
	}
	return false;
}

// 处理入口 
int handle() {
	int i, j;
	for(i = getMinTime(origin); i < 8; ++i) {
		memcpy(arrnow, origin, sizeof(arrnow));
		// 每一轮加深迭代
		if(handleTime(0, i)) return i;
	}
	return 8; 
}

int main() {
	int t = 0;
	int i, j;
	while(scanf("%d\n", &n) == 1 && n > 0) {
		++t;
		for(i = 0; i < n; ++i)
			scanf("%d", &origin[i]);
		j = handle();
		printf("Case %d: %d\n", t, j);
	}
	return 0;	
}