暑假Fourteen宝岛地图

题目背景：

勇敢的水手们到达了一个小岛，在这个小岛上，曾经有海盗在这里埋下了一些宝藏。然而，我们的船快抛锚了，与此同时，船长发现藏宝图的一角被老鼠咬掉了一块。

藏宝图可以用一个n×m大小的矩形表示。矩形中的每一小块表示小岛中的一小块陆地（方块的边长为1米）。有一些方块表示的是海，这些块人是不能通过的。除了海不能走，其它的小方块都是可以行走的。在可行走区域里有一些小方块表示一些已知的地点。

另外，在地图上有k条指令。每条指令的格式表示如下：

“向y方向走n米”。

这里的方向有四种：“北”，“南”，“东”，“西”。如果你正确的跟着这些指令行走，并且完整的执行完所有指令，你就可以找到宝藏所在的地点。

但是，很不幸，由于地图中好多地方都缺失了，船长也不知道从哪些地方开始走。但是船长依然清楚地记得一些已知的地点。另外，船长也知道所有可行走区域。

现在船长想知道从哪些已知地点出发，按照指令，可能找到宝藏所在地。

输入：

单组测试数据 第一行包含两整数n和m（3≤n，m≤1000）。 接下来的n行每行有m个字符，表示整个地图。 “#”代表海。在地图矩形中，矩形的四周一圈一定是海。 “.”代表可行走区域，未知地点。大写字母“A”到“Z”表示可行走区域，已知地点。 所有大写字母不一定都被用到。每个字母在地图中最多出现一次。所有已知地点用不同的大写字母表示。

接下来一行有一个整数k（1≤k≤10^5），接下来有k行。 每行表示一条指令。 指令格式为“dir len”，“dir”表示朝哪个方向走，“len”表示走几步。 “dir”有四种取值“N”，“S”，“E”，“W”，对应题目中的“北”，“南”，“东”，“西” 在地图中，北是在顶部，南是在底部，西是在左边，东是在右边。“len”是一个整数，范围在1，10001，1000。

输出：

共一行，按字典序升序打印出所有可以完整执行地图中指令的已知区域的字母，如果没有满足要求的已知区域，则打印“no solution”（没有引号）。

分析：

关键是先算出每个点向前后左右最大能走的距离。

#include<iostream> #include<set> using namespace std; struct node { int x; int y; int maxN; int maxS; int maxW; int maxE; char c; int type; }; struct ml { int dir; int dis; }; node nodes[1005][1005]; ml mls[100005]; set<char> ans; int main() { int m, n; cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { node nn; char cc; cin >> cc; nn.x = i; nn.y = j; nn.c = cc; if (cc == '#') { nn.type = 0; } else if (cc == '.') { nn.type = 1; } else { nn.type = 2; } nodes[i][j] = nn; } } int nn; cin >> nn; for (int i = 0; i < nn; i++) { char c; cin >> c >> mls[i].dis; if (c == 'N') mls[i].dir = 0; else if (c == 'E') mls[i].dir = 1; else if (c == 'S') mls[i].dir = 2; else mls[i].dir = 3; } for (int i = 0; i < n; i++) {//先从左上到右下计算出每个点向左边和上边的最大距离 for (int j = 0; j < m; j++) { if (nodes[i][j].type == 0) { nodes[i][j].maxN = nodes[i][j].maxW = -1; } else { nodes[i][j].maxN = nodes[i - 1][j].maxN + 1; nodes[i][j].maxW = nodes[i][j - 1].maxW + 1; } } } for (int i = n-1; i >= 0; i--) {//在从右下到左上求出每个点向右边或者下边的最大距离 for (int j = m-1; j >= 0; j--) { if (nodes[i][j].type == 0) { nodes[i][j].maxS = nodes[i][j].maxE = -1; } else { nodes[i][j].maxS = nodes[i + 1][j].maxS + 1; nodes[i][j].maxE = nodes[i][j + 1].maxE + 1; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (nodes[i][j].type == 2) { int ii = i, jj = j; for (int cnt = 0; cnt < nn; cnt++) { ml temp = mls[cnt]; bool flag = true; switch (temp.dir) { case 0: { if (nodes[ii][jj].maxN < temp.dis) { flag = false; } else { ii = ii - temp.dis; } break; } case 1: { if (nodes[ii][jj].maxE < temp.dis) { flag = false; } else { jj = jj + temp.dis; } break; } case 2: { if (nodes[ii][jj].maxS < temp.dis) { flag = false; } else { ii = ii + temp.dis; } break; } case 3: { if (nodes[ii][jj].maxW < temp.dis) { flag = false; } else { jj = jj - temp.dis; } break; } } if (!flag) { break; } if (cnt == nn - 1) { ans.insert(nodes[i][j].c); } } } } } if (ans.empty()) { cout << "no solution" << endl; } else { set<char>::iterator it; for (it = ans.begin(); it != ans.end(); it++) { cout << *it; } } return 0; }

因为每个地图的最外面一圈都是“#”，所以算最大距离的时候不需要考虑前边一个点是否超出了地图范围。