GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

一道不难的题目，即使不用什么剪枝方法，也不会超时，可以AC的。

但是题目有一些隐含条件（或者说是我英语差一些，这道题的有些要求和题目背景放在一起描述，但是这个题目背景我没完全读懂）

首先要根据字典序输出，即'e', 'n', 's', 'w'

然后输入中哪些的阻碍的块是不能穿过的，即使移动起点和终点不在阻碍块上，只是中间路过也不行。

还有，已经访问过的块不能再次被访问，注意这里限制的是每次移动的起点和终点，中间路过已访问过的块是可以的，路过也不能称作“已访问”。

所以实际上是有两种逻辑不同的限制块类型。

AC代码

#include <stdio.h>
#include <string.h>
#define LINENUMMAX 22
#define MAXBLOCKNUM 51int lineNumMax;
// 当前的
int line[LINENUMMAX];
// 全部的
int totalNum;
int lintTotal[5000][LINENUMMAX];
// 已访问过的块
int map[500][500];// 序号从 1 开始
// n上 s下 e右 w左
// 数字 到 字母 字典序
char num2str[5] = {0, 'e', 'n', 's', 'w'};
// 方向对应的坐标移动
char steps[5][2] = {{}, {1, 0}, {0, 1}, {0, -1}, {-1, 0}};
// 方向对应的转90度方向
int truns[5][2] = {{}, {2, 3}, {1, 4}, {1, 4}, {2, 3}};void init()
{int i, x, y, n;scanf("%d", &lineNumMax);scanf("%d", &n);memset(map, 0, sizeof(map));memset(line, 0, sizeof(line));memset(lintTotal, 0, sizeof(lintTotal));for (i = 0; i < n; ++i){scanf("%d %d", &x, &y);map[x + 250][y + 250] = 2;}totalNum = 0;
}// 判断向当前方向走，会不会碰到阻碍 注意这里是移动之前判断
// n 当前长度 i 上一次方向 x,y 当前坐标 xnew ynew 新坐标
bool hasBlock(int i, int x, int y, int xnew, int ynew)
{int a;if (i == 1){for (a = x + 1; a <= xnew; ++a)if (map[a + 250][y + 250] == 2)return true;}if (i == 2){for (a = y + 1; a <= ynew; ++a)if (map[x + 250][a + 250] == 2)return true;}if (i == 3){for (a = ynew; a < y; ++a)if (map[x + 250][a + 250] == 2)return true;}if (i == 4){for (a = xnew; a < x; ++a)if (map[a + 250][y + 250] == 2)return true;}return false;
}// n 当前长度 i 上一次方向 x,y 当前坐标
void dfs(int n, int i, int x, int y)
{int a, newi, xnew, ynew;if (x == 0 && y == 0 && n == lineNumMax){for (a = 0; a < lineNumMax; ++a)lintTotal[totalNum][a] = line[a];totalNum++;return;}if (n >= lineNumMax)return;map[x + 250][y + 250] = 1;for (a = 0; a < 2; ++a){newi = truns[i][a];xnew = x + (n + 1) * steps[newi][0];ynew = y + (n + 1) * steps[newi][1];if (map[xnew + 250][ynew + 250] || hasBlock(newi, x, y, xnew, ynew))continue;line[n] = newi;dfs(n + 1, newi, xnew, ynew);}map[x + 250][y + 250] = 0;
}void computed()
{int i, j;int x, y;// 四个方向都走一遍for (i = 1; i < 5; ++i){line[0] = i;x = steps[i][0];y = steps[i][1];if (map[x + 250][y + 250])continue;dfs(1, i, x, y);}
}int main()
{int co, i, j;scanf("%d", &co);while (co--){init();computed();for (i = 0; i < totalNum; ++i){for (j = 0; j < lineNumMax; ++j)printf("%c", num2str[lintTotal[i][j]]);putchar('\n');}printf("Found %d golygon(s).\n\n", totalNum);}return 0;
}