当前位置:首页 > 图灵资讯 > 技术篇> poj-2056

poj-2056

发布时间:2023-05-24 09:24:47

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)

这个问题是我最害怕的类型,很难转化,没有目标,测试更多的是经验积累,长期训练培养良好的直觉.

上一篇 poj-2709
下一篇 poj-2485

文章素材均来源于网络,如有侵权,请联系管理员删除。

标签: Java教程Java基础Java编程技巧面试题Java面试题