UVa 225 - Golygons (回溯 + 剪枝)
题意
一个人要探索城市。
他有特殊的看风景技巧。
第一次他走一步，停下来看一下风景，然后左转或者右转走2步，看一下风景，再左转或者右转，走3步，看风景。最后走len步正好回到原点。
看过的风景不能再看
求他有几种看风景的方法，输出。
思路
最基本的思路是从起点开始，四个方向搜索、回溯，记录路径。
然后说说我的思路。
我用path记录路径，当判断回到终点的时候就push到vector里。
因为到达后只能左右走或者上下走（二维），所以我分开讨论，当从下面或者上面走来的时候，和当从左边或者右边走来的时候。
关于坐标的处理，可能会有很多很大的障碍物，需要排除。
然后统一加上某个数，相当于原点移位，处理负数。
代码里充斥着大量重复的代码，不优雅。大家看看思路就行。。
有一个相当重要的剪枝，来自帆神(http://blog.csdn.net/accelerator_/article/details/17804417)
如果走到一个地方剩下的步数回不到原点了，直接回溯。
代码
#include <cstdio>
#include <stack>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <cmath>
#define LL long long
#define SZ(x) (int)x.size()
#define Lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
#define MS(arr, num) memset(arr, num, sizeof(arr))
#define PB push_back
#define F first
#define S second
#define ROP freopen("input.txt", "r", stdin);
#define MID(a, b) (a + ((b - a) >> 1))
#define LC rt << 1, l, mid
#define RC rt << 1|1, mid + 1, r
#define LRT rt << 1
#define RRT rt << 1|1
#define BitCount(x) __builtin_popcount(x)
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
using namespace std;
const int MAXN = 200 + 10;
const int MOD = 1e9 + 7;
const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
typedef pair<int, int> pii;
typedef vector<int>::iterator viti;
typedef vector<pii>::iterator vitii;
int len, mp[MAXN][MAXN], vis[MAXN][MAXN];
int sum[30];
const int O = 100;
string str = "nswe";
vector<string> ans;
void DFS(int x, int y, int step, int lastDir, string path)
{
//dir = 0, 下面走来的, 1上面走来, 2右边走来，3左边走来
if (abs(x - O) + abs(y - O) > sum[len] - sum[step]) return;
if (x == O && y == O)
{
if (step == len) ans.PB(path);
return;
}
if (step == len) return;
if (lastDir == 0 || lastDir == 1)
{
for (int i = 2; i < 4; i++)
{
bool flag = false;
int xx = x + dir[i][0] * (step + 1), yy = y + dir[i][1] * (step + 1);
if (xx < 0 || yy < 0) continue;
if (i == 2)
{
for (int k = yy; k < y; k++)
if (mp[xx][k])
{
flag = true;
break;
}
}
else
{
for (int k = y + 1; k <= yy; k++)
if (mp[xx][k])
{
flag = true;
break;
}
}
if (!flag)
if (!mp[xx][yy] && !vis[xx][yy])
{
vis[xx][yy] = 1;
DFS(xx, yy, step + 1, i, path + str[i]);
vis[xx][yy] = 0;
}
}
}
else
{
for (int i = 0; i < 2; i++)
{
bool flag = false;
int xx = x + dir[i][0] * (step + 1), yy = y + dir[i][1] * (step + 1);
if (xx < 0 || yy < 0) continue;
if (i == 0)
{
for (int k = xx; k < x; k++)
if (mp[k][yy])
{
flag = true;
break;
}
}
if (i == 1)
for (int k = x + 1; k <= xx; k++)
if (mp[k][yy])
{
flag = true;
break;
}
if (!flag)
if (!mp[xx][yy] && !vis[xx][yy])
{
vis[xx][yy] = 1;
DFS(xx, yy, step + 1, i, path + str[i]);
vis[xx][yy] = 0;
}
}
}
}
void table()
{
sum[1] = 1;
for (int i = 2; i <= 20; i++) sum[i] = i + sum[i - 1];
}
int main()
{
//ROP;
int T, i, j, nblk;
scanf("%d", &T);
table();
while (T--)
{
ans.clear(); MS(mp, 0);
scanf("%d%d", &len, &nblk);
while (nblk--)
{
int x, y;
scanf("%d%d", &x, &y);
if (abs(x) > O || abs(y) > O) continue;
mp[O - y][x + O] = 1;
}
string path;
for (int i = 0; i < 4; i++)
{
int x = dir[i][0] + O, y = dir[i][1] + O;
vis[x][y] = 1;
if (!mp[x][y])
DFS(x, y, 1, i, path + str[i]);
vis[x][y] = 0;
}
sort(ans.begin(), ans.end());
for (i = 0; i < SZ(ans); i++) cout << ans[i] << endl;
printf("Found %d golygon(s).\n\n", SZ(ans));
}
return 0;
}