UVA 764 Pentominos（搜索)（未AC）

链接：764 - Pentominos

思路：直接DFS去搜索了，加了些剪枝，还是过不了TLE了，答案跑起来感觉挺快的。有谁过了的求交流

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <map>
#include <set>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int d[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
using namespace std;

int t, vis[12], x, y, g[8][8];
typedef pair<int, int> pi;

pi fz(pi p) {
	return make_pair(-p.first, p.second);
}

pi xz(pi p) {
	return make_pair(-p.second, p.first);
}

struct Puz {
	int v[8][5][2];
	int vn;
	Puz() {}
	Puz(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int x5, int y5) {
		vn = 0; int i, j, k, l;
		pi save[5];
		set<pi> s;
		save[0] = make_pair(x1, y1);
		save[1] = make_pair(x2, y2);
		save[2] = make_pair(x3, y3);
		save[3] = make_pair(x4, y4);
		save[4] = make_pair(x5, y5);
		set<set<pi> > ss;
		for (i = 0; i < 2; i++) {
			for (j = 0; j < 4; j++) {
				s.clear();
				for (k = 0; k < 5; k++)
					s.insert(save[k]);
				if (ss.find(s) == ss.end()) {
					int S = 100, B = 100;
					for (k = 0; k < 5; k++) {
						S = min(S, save[k].first);
					}
					for (k = 0; k < 5; k++) {
						v[vn][k][0] = save[k].first - S;
					}
					for (k = 0; k < 5; k++) {
						if (save[k].first - S== 0) {
							B = min(B, save[k].second);
						}
					}
					for (k = 0; k < 5; k++)
						v[vn][k][1] = save[k].second - B;
					vn++;
					ss.insert(s);
				}
				for (k = 0; k < 5; k++) {
					save[k] = xz(save[k]);
				}
			}
			for (j = 0; j < 5; j++) {
				save[j] = fz(save[j]);
			}
		}
	}
} p[12];

void init() {
	p[0] = Puz(0, -2, 0, -1, 0, 0, 0, 1, 0, 2);
	p[7] = Puz(0, -2, 0, -1, 0, 0, 0, 1, 1, 1);
	p[11] = Puz(0, -2, 0, -1, 0, 0, 1, 0, 0, 1);
	p[6] = Puz(0, 0, 0, 1, 0, 2, 1, 0, 1, 1);
	p[4] = Puz(0, -1, 0, 0, 0, 1, 1, 1, 2, 1);
	p[9] = Puz(0, -1, 0, 0, 0, 1, 1, 0, 2, 0);
	p[2] = Puz(0, -1, 0, 0, 0, 1, 1, -1, 1, 1);
	p[1] = Puz(0, 0, -1, 0, 1, 0, 0, -1, 0, 1);
	p[3] = Puz(0, 0, 0, -1, 0, 1, -1, -1, 1, 1);
	p[5] = Puz(0, 0, 0, -1, 0, 1, -1, -1, 1, 0);
	p[10] = Puz(0, 0, -1, 0, -2, 0, 0, 1, 1, 1);
	p[8] = Puz(0, 0, 0, -1, -1, -1, 1, 0, 1, 1);
	
}

inline bool judge(int a, int b, int x, int y) {
	for (int i = 0; i < 5; i++) {
		int xx = x + p[a].v[b][i][0];
		int yy = y + p[a].v[b][i][1];
		if (xx < 0 || xx >= 8 || yy < 0 || yy >= 8 || g[xx][yy] != -1) return false;
	}
	return true;
}

int vv[8][8];

int df(int x, int y) {
	if (x < 0 || x >= 8 || y < 0 || y >= 8 || vv[x][y] || g[x][y] != -1) return 0;
	vv[x][y] = 1;
	int ans = 1;
	for (int i = 0; i < 4; i++) {
		ans += df(x + d[i][0], y + d[i][1]);
	}
	return ans;
}

inline bool ju(int x, int y) {
	memset(vv, 0, sizeof(vv));
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (g[i][j] == -1) {
				if (x > i) return false;
				if (vv[i][j]) continue;
				if (df(i, j) % 5 != 0) return false;
			}
		}
	}
	return true;
}

bool dfs(int x, int y, int num) {
	if (!ju(x, y)) return false;
	
	if (num == 60) {
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				if (g[i][j] == 100) printf("*");
				else printf("%c", g[i][j] + ‘a‘);
			}
			printf("\n");
		}
		return true;
	}
	if (x == 8) return false;
	if (y == 8) return dfs(x + 1, 0, num);
	if (g[x][y] != -1) return dfs(x, y + 1, num);
	for (int i = 0; i < 12; i++) {
		if (vis[i]) continue;
		vis[i] = 1;
		for (int j = 0; j < p[i].vn; j++) {	
			int k;
			if (!judge(i, j, x, y)) continue;
			for (k = 0; k < 5; k++) {
				int xx = x + p[i].v[j][k][0];
				int yy = y + p[i].v[j][k][1];
				g[xx][yy] = i;
			}
			if (dfs(x, y + 1, num + 5)) return true;
			for (k = 0; k < 5; k++) {
				int xx = x + p[i].v[j][k][0];
				int yy = y + p[i].v[j][k][1];
				g[xx][yy] = -1;
			}
			
		}
		vis[i] = 0;
	}
	if (dfs(x, y + 1, num)) return true;
	return false;
}

int main() {
	init();
	
	scanf("%d", &t);
	while (t--) {
		int flag = 0;
		memset(g, -1, sizeof(g));
		memset(vis, 0, sizeof(vis));
		for (int i = 0; i < 4; i++) {
			scanf("%d%d", &x, &y);
			if (x < 1 || x > 8 || y < 1 || y > 8)
				flag = 1;
			g[x - 1][y - 1] = 100;
		}
		if (flag || !dfs(0, 0, 0)) printf("No solution.\n");
		if (t) printf("\n");
	}
	return 0;
}

UVA 764 Pentominos（搜索)（未AC）,布布扣,bubuko.com

UVA 764 Pentominos（搜索)（未AC）

原文：http://blog.csdn.net/accelerator_/article/details/22983257