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

使用dfs遍历所有情况，再去重即可。

遍历部分

遍历的时候需要注意：

1. 这其实并不能算是dfs，因为普通的dfs是一直走到尽头，然后再逐渐退出，走下一条路。到最后的路径是一条线。但是这个题目生成的图形却可以分叉。因此，递归一次dfs时，要循环遍历当前所有的节点，让所有的节点都可以分叉进行。

2. 如果直接遍历所有情况，那么肯定是超时的。我是这样做的：

我一开始尝试了从w*h区域的每个点开始遍历，遇到墙就返回。这样其实存在大量的重复，会重复生成一样的图形。我后面改造成了直接从（1， 1）点开始遍历。并不真实的设立一个墙。在生成的过程中，如果碰到这个图像的宽和高大于区域的大小，那么认为这个区域放不下这个图形，就退出。这中间出现坐标负值也是正常的。

3. 用上面的方法之后，还是有较多的超时。因此我们继续优化。这时候我们设定一个中间图形是否遍历过的set。假设该图形或者该图形的旋转，平移和镜像在set中存在了，就说明已经遍历过了，就不在往下进行。这样能够很大的缩小情况的种类。比如：[(1,1), (1,2)] 和 [(1,1), (2,1)] 等等都属于重复图形，也就是说，dfs的第二层依旧只有一个结点。这样节约的时间是很多的。

4. 用了上面的方法后，还是超时。但是即使输出全部的情况下，在本地电脑中也是比较快的，大概一两分钟左右。由于情况不多（不超过1000中情况），因此直接打表更适合。即我们在本地算出结果，把结果直接写在代码里。我直接在代码中写了n=10情况下的所有输出，其他情况下还是实时计算的。这样最后AC了。

如何对图形进行的旋转，平移和镜像

除了遍历之外，还有一个注意的点就是，如何对图形进行的旋转，平移和镜像。且能在set中标识这个图形。

1. 标识图形

由于每个点的的最大坐标为(1-10,1-10），最多10个点，因此标识所有情况需要 10^20。64位存不下。换一种表示法，用起点加转向，就是100*4^9， 64位存下绰绰有余。但是我们并不是一条路径，可以有分叉，因此这种方式做不到。

还有一个问题就是，存在set中的结构要保证唯一性，即同样一个图形，如果点的位置不一致，也可以找到。这时候我们就想到用set存储单个图形。然后单个图形的set元素是一个int，里面的值是100 * x + y。由于set是排好序的，因此我们的点在里面就是天然排序的，先按照x值排序，在按照y值排序。这样可以保证点不会因为位置交换了而判断为两个图形。

当然，100 * x + y的方法在遇到负值是有很大的问题，后面我又进行了改进。网络上还有人用其他方法可以存储单个点的，也可以参考。假设我们的点是（1， -1），那么值是-99。还原回点的时候，就变成了（0， -99）。

我的解决方案是，让值保持整数: 100 * x + y  ——>  100 *(x+20) + y + 20。由于坐标最大为10，因此计算的结果肯定是正的，还原回来也肯定是正的。

2. 平移

平移非常简单，我们让以x坐标和y坐标最小值为基准，设为1。其他的点平移这个差值即可。

这个平移的作用实际上是标准化，即将在不同位置的图形，都平移到一个位置，如果他是一个图形，那么平移之后位置是一致的。

3. 旋转图形

我们只需要实现转90度的方法即可。转两次就是180，三次就是270。

向右转90度，对于图形来说，坐标变化就是：（x， y） -> （y， -x）。画个图试一下就能看出规律了。因此，每次旋转时我们执行这个变化即可。

旋转之后还要平移一次。

4. 镜像图形

我们随便横向镜像和纵向镜像都可以，因此横向镜像后转90度就变为纵向镜像了。镜像更简单，x或者y的符号变一下即可。这时候我们注意到一点：

如果我们的点坐标是0，镜像完还是0，那肯定是不正确的。因此坐标从1开始，即1 - 10。1的前一个点是-1，我们没有0这个点。这时候平移和遍历就出问题了：

1和-1中间的差值是2不是1，我们如果正常遍历， 会走到0这个点。我们平移的时候如果图形中间穿过0这条线，那么减的值是不正确的。因此，我们要相应做处理，如果坐标值碰到0，根据情况设为1或者-1。平移的时候区分中间有0和没有0的情况。

AC代码

#include<stdio.h>
#include<string>
#include<string.h>
#include<set>using namespace std;int n, w, h;
int steps[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// 数量
int num;
set<int> seArr, seTemp;
set<set<int>> se;
int arrTemp[10][2];
// 该状态是否访问过 
set<set<int>> seFlag;int tenTable[1000] = {0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,16,68,108,117,118,0,0,0,21,277,842,1226,1329,1338,1339,0,0,21,287,1847,3234,3773,3876,3885,3886,0,1,277,1847,2376,4003,4542,4645,4654,4655,0,16,842,3234,4003,4003,4542,4645,4654,4655,0,68,1226,3773,4542,4542,4542,4645,4654,4655,0,108,1329,3876,4645,4645,4645,4645,4654,4655,0,117,1338,3885,4654,4654,4654,4654,4654,4655,1,118,1339,3886,4655,4655,4655,4655,4655,4655};void getXY(int res, int &x, int &y) {x = res / 100 - 20;y = res % 100 - 20;
}void output(set<int> &setTemp) {int x, y;for(auto ip = setTemp.begin(); ip != setTemp.end(); ++ip) {getXY(*ip, x, y);printf("[%d,%d] ", x, y);}putchar('\n');
}int setXY(int x, int y) {return (x + 20) * 100 + y + 20;
}// 规范化 最小的x为 1 最小的y为 1
void standard(int (* arr)[2], int ntemp) {int i;int minX = arr[0][0], minY = arr[0][1];for(i = 1; i < ntemp; ++i) {if(arr[i][0] < minX) minX = arr[i][0];if(arr[i][1] < minY) minY = arr[i][1];}for(i = 0; i < ntemp; ++i) {if(arr[i][0] * minX > 0)arr[i][0] = arr[i][0] - minX + 1;elsearr[i][0] = arr[i][0] - minX;if(arr[i][1] * minY > 0)arr[i][1] = arr[i][1] - minY + 1;elsearr[i][1] = arr[i][1] - minY;}
}// 点的数组转为set 
void arr2Set(set<int> &setTemp, int (* arr)[2], int ntemp) {setTemp.clear();for(int i = 0; i < ntemp; ++i) {setTemp.insert(setXY(arr[i][0], arr[i][1]));}
}// set转为点的数组
void set2Arr(set<int> &setTemp, int (* arr)[2]) {int i = 0;for(auto ip = setTemp.begin(); ip != setTemp.end(); ++ip, ++i) {getXY(*ip, arr[i][0], arr[i][1]);}
}// 向右旋转90度
void turnRight(int (* arr)[2], int ntemp) {int j;for(int i = 0; i < ntemp; ++i) {j = arr[i][1];arr[i][1] = -arr[i][0];arr[i][0] = j;}
}// 镜像反转
void reserveArr(int (* arr)[2], int ntemp) {for(int i = 0; i < ntemp; ++i) {arr[i][0] = -arr[i][0]; }
}void judge(set<int> &setTemp) {if(se.count(setTemp)) return;++num;se.insert(seTemp);
}bool isBumpWall(set<int> &setTemp) {auto ip = setTemp.begin();int x, y;getXY(*ip, x, y);int minX = x, minY = y, maxX = x, maxY = y;for(ip = setTemp.begin(); ip != setTemp.end(); ++ip) {getXY(*ip, x, y);if(x < minX) minX = x;if(y < minY) minY = y;if(x > maxX) maxX = x;if(y > maxY) maxY = y;}x = maxX - minX - (maxX * minX < 0 ? 1 : 0);y = maxY - minY - (maxY * minY < 0 ? 1 : 0);if(((x >= w || y >= h) && (x >= h || y >= w)) || x + y >= n) return true;return false; 
} // 该模式的几种变形是否访问过 
bool findModel(int (* arr)[2], set<int> &setTemp, int ntemp) {if(seFlag.count(setTemp)) return true;int i;for(i = 0; i < 3; ++i) {// 转90度turnRight(arrTemp, ntemp);standard(arrTemp, ntemp);arr2Set(setTemp, arrTemp, ntemp);if(seFlag.count(setTemp)) return true;}// 镜像反转reserveArr(arrTemp, ntemp);for(i = 0; i < 4; ++i) {// 转90度if(i != 0) turnRight(arrTemp, ntemp);standard(arrTemp, ntemp);arr2Set(setTemp, arrTemp, ntemp);if(seFlag.count(setTemp)) return true;}return false; 
}void dfs(int count) {++count;int i, x, y, xi, yi, resi;for(auto ip = seArr.begin(); ip != seArr.end(); ++ip) {getXY(*ip, x, y);for(i = 0; i < 4; ++i) {xi = steps[i][0] + x;yi = steps[i][1] + y;if(xi == 0) {if(steps[i][0] > 0) xi = 1;if(steps[i][0] < 0) xi = -1;}if(yi == 0) {if(steps[i][1] > 0) yi = 1;if(steps[i][1] < 0) yi = -1;}resi = setXY(xi, yi);if(seArr.count(resi)) continue;seArr.insert(resi);set2Arr(seArr, arrTemp);standard(arrTemp, count);arr2Set(seTemp, arrTemp, count);if(!isBumpWall(seArr) && !findModel(arrTemp, seTemp, count)) {// 设置访问标记 seFlag.insert(seTemp);if(count == n) judge(seTemp);else dfs(count);}seArr.erase(resi);}}
}int compute() {num = 0;se.clear();seFlag.clear();seArr.clear();seArr.insert(setXY(1, 1));dfs(1);return num;
}int main() {while(scanf("%d %d %d", &n, &w, &h) == 3) {if(w * h < n) {printf("0\n");continue;}if(w * h == n || n == 1) {printf("1\n");continue;}if(n == 10) {printf("%d\n", tenTable[(w-1)*10 + h-1]);continue;}printf("%d\n", compute());}return 0;
}