736K 0MS G++
// 736K 0MS G++ #include <cstdio> #include <cstring> #include <queue> using namespace std; #define MAX 300 #define SEP 'S' #define INF -99999 // int LineSInfo[MAX][2]; // MAX line, every line: [0] store S begin pos [1] store S end pos in this line char LineSInfo[MAX][MAX]; char pointFlag[MAX][MAX]; // 0 white, 1 grey, 2 black struct LineSExpandOption { char expand; char noExpand; }; typedef struct LineSExpandOption LineSExpandOption; LineSExpandOption lineSExpandOption[MAX]; int M; int N; struct Point { int x; int y; char used; int step; }; typedef struct Point Point; Point beginPoints[2]; Point endPoints[2]; queue<Point> pointQueue; void pushPoint(int x, int y, int step) { // printf("pushPoint %d %d %d\n", x, y, step); pointFlag[x][y] = 1; Point newPoint; newPoint.x = x; newPoint.y = y; newPoint.step = step; pointQueue.push(newPoint); } int bfs(Point begin, Point end) { pointQueue.push(begin); pointFlag[begin.x][begin.y] = 1; while(pointQueue.size()) { Point curPoint = pointQueue.front(); pointQueue.pop(); int curX = curPoint.x; int curY = curPoint.y; int curSteps = curPoint.step; // printf("curX %d curY %d curSteps %d\n", curX, curY, curSteps); if (curY == N-1) { return curSteps; } if ((curX+1 <= M-1) && (LineSInfo[curY][curX+1] == SEP) && !pointFlag[curX+1][curY]) { // left pushPoint(curX+1, curY, curSteps+1); } if ((curX-1) >= 0 && (LineSInfo[curY][curX-1] == SEP) && !pointFlag[curX-1][curY]) { // right pushPoint(curX-1, curY, curSteps+1); } if ((curY+1) <= N-1 && (LineSInfo[curY+1][curX] == SEP) &&!pointFlag[curX][curY+1]) { // up pushPoint(curX, curY+1, curSteps+1); } if ((curY-1) >= 0 && (LineSInfo[curY-1][curX] == SEP) && !pointFlag[curX][curY-1]) { //down pushPoint(curX, curY-1, curSteps+1); } pointFlag[curX][curY] = 2; } return -1; } void getShortestSep() { // printf("getShortestSep\n"); int minStep = 999999; for (int i = 0; i < 2; i++) { // for (int j = 0; j < 2; j++) { if (beginPoints[i].used) { beginPoints[i].step = 0; memset(pointFlag, 0, sizeof(pointFlag)); while(pointQueue.size()) { pointQueue.pop(); } // printf("%d %d %d %d\n", beginPoints[i].x, beginPoints[i].y, // endPoints[j].x, endPoints[j].y); int res = bfs(beginPoints[i], endPoints[0]); if (res != -1) { minStep = (res + 1) < minStep ? (res + 1) : minStep; } // printf("%d\n", res); } // } } // if (beginPoints[0].used) { // memset(pointFlag, 0, sizeof(pointFlag)); // int res = bfs(beginPoints[0], endPoints[0]); // if (res != -1) { // minStep = (res + 1) < minStep ?= -1) { // minStep = (res + 1) < minStep ? (res + 1) : minStep; // } // } printf("%d\n", minStep == 999999 ? -1 : minStep); } int main() { while(1) { scanf("%d %d", &N, &M); if (!M && !N) { return 0; } memset(lineSExpandOption, 0, sizeof(lineSExpandOption)); memset(beginPoints, 0, sizeof(beginPoints)); memset(endPoints, 0, sizeof(endPoints)); for (int i = 0; i < N; i++) { scanf("%s", LineSInfo[i]); int j; for (j = M-2; LineSInfo[i][j] != SEP; j--) { } // printf("%d\n", j); LineSInfo[i][j+1] = SEP; for (j = M-2; LineSInfo[i][j] != SEP; j--) { // if (LineSInfo[i][j] == SEP) { // beginPoints[0].x = j; // beginPoints[0].y = 0; // beginPoints[0].used = 1; // break; // } } if (i == 0) { // first line begin ponit if (j < M-1) { // not first, can be begin beginPoints[0].x = j; beginPoints[0].y = 0; beginPoints[0].used = 1; } if (j > 0 && (LineSInfo[i][j-1] == SEP)) { // not last-1, can be begin beginPoints[1].x = j-1; beginPoints[1].y = 0; beginPoints[1].used = 1; } } // else if (i == N-1) { // last line end point // if (j < M-1) { // not first, can be begin // endPoints[0].x = j; // endPoints[0].y = N-1; // endPoints[0].used = 1; // } // if (j > 0 && (LineSInfo[i][j-1] == SEP)) { // not last-1, can be begin // endPoints[1].x = j-1; // endPoints[1].y = N-1; // endPoints[1].used = 1; // } // } } getShortestSep(); } }几次WA... 各种低级错误
先是M N搞反，数组坐标系搞反，然后BFS前没有清空queue，
这个问题是理解问题意义难、转化难、求解简单的典型问题.
一开始并没有完全理解问题的意思，以为improvement可以做几次，然后要求最短的seperator，
后来才发现improvement是一次，
起初，我遵循了纯模拟的想法。当我走到一半时，我发现我根本解决不了它（后来，似乎有人用这种类似的想法解决了它，但我觉得它偏向于智力问题）
后来仔细想了想，才发现这个问题其实是BFS从上到下寻求的最短路径(路径是seperator， 路径最短，seperator的vetext必然最少)
只是如何得到这个图G需要一些思考，
首先，原seperator(以下简称sep)中的vetex必然属于G，但G不止这些点，因为improvement需要进行， 在improve之后，任何与S相邻的B都可能成为新的S，
这样，那些邻接S的B也可以加入G，这样G的vetex就全了，
为了方便后面的BFS，可以先预处理字符串，把合格的B变成S。
将整个输入字符串转换为二维矩阵C(请注意，C[Y][X]应该是X Y 坐标系倒置，以为C[i]代表字符串矩阵的某一行，C[i][j]这一行的第j列，正好是X 和 Y颠倒了）
然后是BFS需要的flag矩阵，用来标记一个节点是否已经遍历过，
接下来是BFS的实际位置。首先，它必须从第一行开始，但可能有两个起点：（一个是improve之前SEP的起点，另一个是前一个起点右侧的B）
这里的细节是，标题规定起点不能是第一行的两个端点，因此有必要判断这两点是否能满足。
终点更好，只需要到达最后一行，必须是终点（因为满足SEP条件），这里也可能判断前后端点，但我没有做，似乎问题数据相对较弱，只有最后一行判断可能得到一个终点是前后端点的终点，这不满足问题的意义，这里标记问题。最安全的是找出可能的终点(或者，最后一行和最后一行相接处的附近点是)。
下一步是对每个起点进行常规BFS，寻求最短的路径(四个方向，上下左右，无斜向，根据其值是否为S和flag 还有 是否越界 决定是否通过，注意节点的路径长度，以便最终输出总路径长度），最小值是SEP的最短长度，+1（点比边缘多1）
这个问题是我最害怕的类型，很难转化，没有目标，测试更多的是经验积累，长期训练培养良好的直觉.
湘公网安备43019002002060