POJ 1101 解题报告-白红宇

POJ 1101 解题报告

阅读量：4203 次

发布时间：2019-05-26

本文共 2536 字，大约阅读时间需要 8 分钟。

这道题是BFS题。需要注意题意理解：最少segments而不是最短路径。由于边界可以出去，所以实现的时候需要注意坐标。

例子之间没有输出空行WA了一次。输入错误WA了多次（最后输入是逐个输入字符，而不是输入行）。

Accepted

220K

16MS

2835B

/* ID: thestor1 LANG: C++ TASK: poj1101 */#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;const int MAXW = 75;const int MAXH = 75;bool isBorder(int x, int y, int H, int W) { return x == 0 || y == 0 || x == H + 1 || y == W + 1;}int main(){ int directions[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // extra width for '\n' and `\0` in the end char board[MAXH][MAXW + 3]; int dis[MAXH + 2][MAXW + 2]; int W, H, t = 0; int x1, y1, x2, y2; while (scanf("%d%d", &W, &H) > 0 && W && H) { t++; // for (int h = 0; h < H; ++h) { // fgets(board[h], W + 2, stdin); // // scanf("%[^\n]s", board[h]); // } for (int h = 0; h < H; ++h) { // ignore the '\n' char newline = getchar(); // printf("[debug]newline: [%c]\n", newline); assert(newline == '\n'); for(int w = 0; w < W; ++w) { board[h][w] = getchar(); // printf("[debug]board[%d][%d]: [%c]\n", h, w, board[h][w]); } } // printf("[debug]board:\n"); // for (int h = 0; h < H; ++h) { // for (int w = 0; w < W; ++w) { // printf("%c", board[h][w]); // } // printf("\n"); // } printf("Board #%d:\n", t); int pno = 0; while (scanf("%d%d%d%d", &y1, &x1, &y2, &x2) > 0) { pno++; // printf("[debug]%d %d %d %d\n", x1, y1, x2, y2); if (!x1 && !y1 && !x2 && !y2) { break; } for (int h = 0; h <= H + 1; ++h) { for (int w = 0; w <= W + 1; ++w) { dis[h][w] = -1; } } dis[x1][y1] = 0; queue
                  
                   
                     > que; que.push(make_pair(x1, y1)); while (!que.empty()) { pair
                    
                      cur = que.front(); que.pop(); int x = cur.first, y = cur.second; // printf("[debug]cur: (%d, %d), dis: %d\n", x, y, dis[x][y]); if (x == x2 && y == y2) { break; } for (int d = 0; d < 4; ++d) { int nx = x, ny = y; bool canMove = true; while (canMove) { nx += directions[d][0]; ny += directions[d][1]; canMove = false; if (0 <= nx && nx <= H + 1 && 0 <= ny && ny <= W + 1 && dis[nx][ny] < 0) { dis[nx][ny] = dis[x][y] + 1; if (isBorder(nx, ny, H, W) || board[nx - 1][ny - 1] != 'X') { que.push(make_pair(nx, ny)); canMove = true; } } } } } // printf("[debug]dis:\n"); // for (int i = 0; i <= H + 1; ++i) { // for (int j = 0; j <= W + 1; ++j) { // printf("%2d ", dis[i][j]); // } // printf("\n"); // } printf("Pair %d: ", pno); if (dis[x2][y2] >= 0) { printf("%d segments.\n", dis[x2][y2]); } else { printf("impossible.\n"); } } printf("\n"); } return 0; }