[POJ 1084] Square Destroyer【IDDFS / IDA*】

  • 2018-01-02
  • 0
  • 0

Problem:

Time Limit: 1000MS Memory Limit: 10000K

Description

The left figure below shows a complete 3*3 grid made with 2*(3*4) (=24) matchsticks. The lengths of all matchsticks are one. You can find many squares of different sizes in the grid. The size of a square is the length of its side. In the grid shown in the left figure, there are 9 squares of size one, 4 squares of size two, and 1 square of size three.

Each matchstick of the complete grid is identified with a unique number which is assigned from left to right and from top to bottom as shown in the left figure. If you take some matchsticks out from the complete grid, then some squares in the grid will be destroyed, which results in an incomplete 3*3 grid. The right figure illustrates an incomplete 3*3 grid after removing three matchsticks numbered with 12, 17 and 23. This removal destroys 5 squares of size one, 3 squares of size two, and 1 square of size three. Consequently, the incomplete grid does not have squares of size three, but still has 4 squares of size one and 1 square of size two.


As input, you are given a (complete or incomplete) n*n grid made with no more than 2n(n+1) matchsticks for a natural number 5 <= n . Your task is to compute the minimum number of matchsticks taken
out to destroy all the squares existing in the input n*n grid.

Input

The input consists of T test cases. The number of test cases (T ) is given in the first line of the input file.
Each test case consists of two lines: The first line contains a natural number n , not greater than 5, which implies you are given a (complete or incomplete) n*n grid as input, and the second line begins with a nonnegative integer k , the number of matchsticks that are missing from the complete n*n grid, followed by
k numbers specifying the matchsticks. Note that if k is equal to zero, then the input grid is a complete n*n grid; otherwise, the input grid is an incomplete n*n grid such that the specified k matchsticks are missing from the complete n*n grid.

Output

Print exactly one line for each test case. The line should contain the minimum number of matchsticks that have to be taken out to destroy all the squares in the input grid.

Sample Input

2
2
0
3
3 12 17 23

Sample Output

3
3

Source

Taejon 2001

Solution:

采用 IDDFS 的思想,每次找出最小完整正方形,尝试破坏其每一条边

储存每个正方形边上的火柴编号 sq[].stk[] 和每根火柴所在的正方形编号 st[].sqr[],并用 sqDestroy[] 表示每个正方形被破坏的边数。

构造正方形时一定要先推清楚式子,不要忘记清零。详见 Code #1

Code #1 通过 1 5 0 这组极限数据需要十几秒,但由于数据非常水,在 POJ 上可以 AC。

可以在此基础上进行优化,将 IDDFS 改造成 IDA* 算法 (Iterative Deepening A-star Algorithm)

估价函数 h():每次破坏整个最小完整正方形,但只算作一次操作。详见 Code #2

Code #1: O(玄学) [176K, 16MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int T, n, k, maxdep;

struct Square{
	int stk[22], top;
} sq[62];

struct Stick{
	int sqr[20], top;
} st[62];

int topsq;

inline void squareConstruct(const int &sqId, const int &leftup, const int &edgeSize){
	sq[sqId].top = 0;
	for(register int i = 0; i < edgeSize; i++){
		int curId = leftup + i;  // Up-side edge
		sq[sqId].stk[++sq[sqId].top] = curId;
		st[curId].sqr[++st[curId].top] = sqId;
	}
	for(register int i = 0; i < edgeSize; i++){
		int curId = leftup + ((n << 1) + 1) * edgeSize + i;  // Down-side edge
		sq[sqId].stk[++sq[sqId].top] = curId;
		st[curId].sqr[++st[curId].top] = sqId;
	}
	for(register int i = 0; i < edgeSize; i++){
		int curId = leftup + n + ((n << 1) + 1) * i;  // Left-side edge
		sq[sqId].stk[++sq[sqId].top] = curId;
		st[curId].sqr[++st[curId].top] = sqId;
	}
	for(register int i = 0; i < edgeSize; i++){
		int curId = leftup + n + edgeSize + ((n << 1) + 1) * i;  // Right-side edge
		sq[sqId].stk[++sq[sqId].top] = curId;
		st[curId].sqr[++st[curId].top] = sqId;
	}
}

int sqDestroy[62];  // The number of the sticks that a square misses

inline void destroyStick(int stickId) {for(register int i = 1; i <= st[stickId].top; i++) sqDestroy[st[stickId].sqr[i]]++;}

inline void recoverStick(int stickId) {for(register int i = 1; i <= st[stickId].top; i++) sqDestroy[st[stickId].sqr[i]]--;}

inline bool IDDFS(int dep){
	int minsq;
	for(minsq = 1; minsq <= topsq; minsq++)
		if(!sqDestroy[minsq]) break;
	if(minsq > topsq) return 1;  // All the squares are destroyed
	if(dep >= maxdep) return 0;
	for(register int i = 1; i <= sq[minsq].top; i++){
		destroyStick(sq[minsq].stk[i]);
		if(IDDFS(dep + 1)) return 1;
		recoverStick(sq[minsq].stk[i]);
	}
	return 0;
}

int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d%d", &n, &k);
		topsq = 0;
		for(register int i = 1; i < 62; i++) sq[i].top = st[i].top = 0;  // Beware of the initialization !!!
		for(register int edgeSize = 1; edgeSize <= n; edgeSize++)
			for(register int i = 1; i <= n - edgeSize + 1; i++)
				for(register int j = 1; j <= n - edgeSize + 1; j++){
					int leftup = ((n << 1) + 1) * (i - 1) + j;
					squareConstruct(++topsq, leftup, edgeSize);
				}
		memset(sqDestroy, 0, sizeof(sqDestroy));
		for(register int i = 1; i <= k; i++){
			int desId;
			scanf("%d", &desId);
			destroyStick(desId);
		}
		for(maxdep = 0;; maxdep++){
			if(IDDFS(0)){
				printf("%d\n", maxdep);
				break;
			}
		}
	}
	return 0;
}

Code #2: O(玄学) [176K, 0MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int T, n, k, maxdep;

struct Square{
	int stk[22], top;
} sq[62];

struct Stick{
	int sqr[20], top;
} st[62];

int topsq;

inline void squareConstruct(const int &sqId, const int &leftup, const int &edgeSize){
	sq[sqId].top = 0;
	for(register int i = 0; i < edgeSize; i++){
		int curId = leftup + i;  // Up-side edge
		sq[sqId].stk[++sq[sqId].top] = curId;
		st[curId].sqr[++st[curId].top] = sqId;
	}
	for(register int i = 0; i < edgeSize; i++){
		int curId = leftup + ((n << 1) + 1) * edgeSize + i;  // Down-side edge
		sq[sqId].stk[++sq[sqId].top] = curId;
		st[curId].sqr[++st[curId].top] = sqId;
	}
	for(register int i = 0; i < edgeSize; i++){
		int curId = leftup + n + ((n << 1) + 1) * i;  // Left-side edge
		sq[sqId].stk[++sq[sqId].top] = curId;
		st[curId].sqr[++st[curId].top] = sqId;
	}
	for(register int i = 0; i < edgeSize; i++){
		int curId = leftup + n + edgeSize + ((n << 1) + 1) * i;  // Right-side edge
		sq[sqId].stk[++sq[sqId].top] = curId;
		st[curId].sqr[++st[curId].top] = sqId;
	}
}

int sqDestroy[62];  // The number of the sticks that a square misses

inline void destroyStick(int stickId) {for(register int i = 1; i <= st[stickId].top; i++) sqDestroy[st[stickId].sqr[i]]++;}

inline void recoverStick(int stickId) {for(register int i = 1; i <= st[stickId].top; i++) sqDestroy[st[stickId].sqr[i]]--;}

int tmp[62];

inline int h(){  // Evaluation Function: every time destroy all sticks of one square, but only calculate it as one step.
	int ret = 0;
	for(register int i = 1; i <= topsq; i++) tmp[i] = sqDestroy[i];
	while(1){
		int minsq;
		for(minsq = 1; minsq <= topsq; minsq++)
			if(!sqDestroy[minsq]) break;
		if(minsq > topsq) break;
		ret++;
		for(register int i = 1; i <= sq[minsq].top; i++) destroyStick(sq[minsq].stk[i]);
	}
	for(register int i = 1; i <= topsq; i++) sqDestroy[i] = tmp[i];
	return ret;
}

inline bool IDAstar(int dep){
	int minsq;
	for(minsq = 1; minsq <= topsq; minsq++)
		if(!sqDestroy[minsq]) break;
	if(minsq > topsq) return 1;  // All the squares are destroyed
	if(dep + h() > maxdep) return 0;
	for(register int i = 1; i <= sq[minsq].top; i++){
		destroyStick(sq[minsq].stk[i]);
		if(IDAstar(dep + 1)) return 1;
		recoverStick(sq[minsq].stk[i]);
	}
	return 0;
}

int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d%d", &n, &k);
		topsq = 0;
		for(register int i = 1; i < 62; i++) sq[i].top = st[i].top = 0;  // Beware of the initialization !!!
		for(register int edgeSize = 1; edgeSize <= n; edgeSize++)
			for(register int i = 1; i <= n - edgeSize + 1; i++)
				for(register int j = 1; j <= n - edgeSize + 1; j++){
					int leftup = ((n << 1) + 1) * (i - 1) + j;
					squareConstruct(++topsq, leftup, edgeSize);
				}
		memset(sqDestroy, 0, sizeof(sqDestroy));
		for(register int i = 1; i <= k; i++){
			int desId;
			scanf("%d", &desId);
			destroyStick(desId);
		}
		for(maxdep = 0;; maxdep++){
			if(IDAstar(0)){
				printf("%d\n", maxdep);
				break;
			}
		}
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai