UVa 225 Golygons 黄金图形 暴力搜索 剪枝 状态判断

题目链接：Golygons
题目描述：

给定$n$和$k$个障碍物的坐标，你需要走$n$次，第一次走一个单位距离，第二次走二个单位距离，…，第$n$次走$n$个单位距离。走得过程中不能穿过或者到达障碍物所在的点，你走得方向为东南西北（也就是上下左右），但是需要注意的是，你每走一步你必须进行一次$90°$的转向，输出所有能够从$(0,0)$出发并且回到$(0,0)$位置的路径。
例如下图是一种合理的路径。

输出用$news$组成的字母表示。

题解：

本题我们从原点开始搜索下一次移动后的位置，并且我们判断移动路径上是否存在障碍物，如果不存在我们才能移动，同时需要判断到达的点我们之前是否到达过。这样在$n$次移动之后我们只需要判断是否回到了原点。
可以使用的剪枝：如果我们当前位置的横纵坐标的和大于剩下可以走得步数，那么我们可以直接进行剪枝。

代码：
注：最好不用$STL$，我开始用$STL$如果不开$O2$的话会超时

#include <bits/stdc++.h>const int MAX_COORDINATE = (1 + 20) * 20 / 2 / 2; // 移动要想回到原点最多20步走的最大距离的一半
const int o = MAX_COORDINATE; // 为了处理负数，我们将所有的坐标全部进行一次移动using namespace std;int T, n, k, x, y, ans;
bool block[(MAX_COORDINATE << 1) + 1][(MAX_COORDINATE << 1) + 1], vis[(MAX_COORDINATE << 1) + 1][(MAX_COORDINATE << 1) + 1];
string path;// 按字典序从小到大返回direction转向90度形成的方向
string getDirection(char direction)
{if (direction == 0) { return "ensw"; }else if (direction == 'e') { return "ns"; }else if (direction == 's') { return "ew"; }else if (direction == 'w') { return "ns"; }else { return "ew"; }
}// 朝某个方向走step步
void move(int &x, int &y, char direction, int step)
{if (direction == 'e') { x += step; }else if (direction == 'w') { x -= step; }else if (direction == 'n') { y += step; }else { y -= step; }
}// 判断路径上是否有障碍物
bool blocked(int a1, int b1, int a2, int b2)
{if (a1 == a2) {if (b1 > b2) { swap(b1, b2); }while(b1 <= b2) {if (block[a1][b1]) { return true; }b1++;}} else if (b1 == b2) {if (a1 > a2) {swap(a1, a2); }while(a1 <= a2) {if (block[a1][b1]) { return true; }a1++;}}return false;
}void dfs(int nowDepth, char lastDirection)
{if (nowDepth == n) {if (x == o && y == o) {ans++;cout << path << endl;}return;}if (abs(x - o) + abs(y - o) - (nowDepth + 1 + n) * (n - nowDepth) / 2 > 0) { return; }string direction = getDirection(lastDirection);for (char nowDirection : direction) {int tempX = x, tempY = y;int nx = x, ny = y;move(nx, ny, nowDirection, nowDepth + 1);if (vis[nx][ny] || blocked(x, y, nx, ny)) { continue; }vis[nx][ny] = true;x = nx, y = ny;path.push_back(nowDirection);dfs(nowDepth + 1, nowDirection);vis[nx][ny] = false;x = tempX, y = tempY;path.pop_back();}
}int main()
{ios::sync_with_stdio(false);cin >> T;while(T--) {cin >> n >> k;memset(vis, 0, sizeof(vis));memset(block, 0, sizeof(block));for (int i = 0; i < k; i++) {cin >> x >> y;if (abs(x) > MAX_COORDINATE || abs(y) > MAX_COORDINATE) { continue; } // 在范围外的不论如何都不会撞到block[x + MAX_COORDINATE][y + MAX_COORDINATE] = true;}ans = 0;x = y = o;path = "";dfs(0, 0);cout << "Found " << ans << " golygon(s)." << endl << endl;}return 0;
}