UVa 225 – Golygons [DFS+剪枝]

距离100题还有4道,此时最忌讳急于求成,所以打算做题不看题解,有时候一道题很难需要想很多甚至做好几天都不能AC,但正是自己不断修改错误,优化代码,才使得自己的编程水平有进步,最后的AC才更加有成就感。

这道题思路还算简单,但是需要加各种剪枝条件,如当前做到达的地方能否再走n-d步到达原点,我感觉像是A*算法,提前估计当前状态还需要扩展几层才能得到目标状态。

经历了三次TLE,总结一下优化手段:

1.关闭输入输出缓冲同步,实现cin和cout跟scanf和printf几乎相同的速度,即加入代码:

ios::sync_with_stdio(false);

2.去掉所有STL存储的东西,能用数组存储的就用数组存,并且会发现有些时候数组操作起来更加方便,特别是DFS。

3.数组内查找某个元素是否存在,理论上find要比count快。

4.其他就是根据题目加各种剪枝了。

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

struct dot{
	int x, y;
	dot(int x = 0, int y = 0) : x(x), y(y) {}
	bool operator == (const dot & rhs) const{
		return x == rhs.x && y == rhs.y;
	}
};
int n, k, cnt = 0;
const int dir[4][2] = { { 1, 0 }, { 0, 1 }, { 0, -1 }, { -1, 0 } };  //东 北 南 西
const char dict[4] = { 'e', 'n', 's', 'w' };
int note[1024];
dot block[64], vis[1024];

void DFS(int curdir, int d, int x, int y)
{
	if (d == n){
		if (x || y) return;
		for (int i = 0; i < n; ++i)
			printf("%c", dict[note[i]]);
		printf("\n"); ++cnt; return;
	}
	for (int i = 0; i < 4; ++i){
		if ((i == 0 || i == 3) && (curdir == 0 || curdir == 3)) continue;
		if ((i == 1 || i == 2) && (curdir == 1 || curdir == 2)) continue;
		dot v(x, y);
		if ((n - d - 1)*n < abs(v.x + (d + 1)*dir[i][0]) + abs(v.y + (d + 1)*dir[i][1]))
			goto loop;
		for (int j = 0; j < d + 1; ++j){
			v.x += dir[i][0];
			v.y += dir[i][1];
			if (find(block, block + k, v) != block + k)
				goto loop;
		}
		if (find(vis, vis + d, v) == vis + d){
			vis[d] = v; note[d] = i;
			DFS(i, d + 1, v.x, v.y);
		}
	loop:;
	}
}
void init()
{
	cnt = 0;
	memset(vis, 0, sizeof(vis));
	memset(block, 0, sizeof(block));
	memset(note, 0, sizeof(note));
}
int main()
{
	ios::sync_with_stdio(false);
	int T; cin >> T;
	while (init(), T--){
		cin >> n >> k;
		for (int i = 0; i < k; ++i){
			dot t; cin >> t.x >> t.y;
			block[i] = t;
		}
		DFS(-1, 0, 0, 0);
		printf("Found %d golygon(s).\n\n", cnt);
	}
	return 0;
}

 

欢迎留言