检测bfs中的路径

问题描述 投票:0回答:1

我正在做一个标准问题来计算由骑士达到目标的最小动作,但我也想跟踪路径,但它显示错误。显示错误

prog.cpp: In function 
   'int minStepToReachTarget(int*, int*, int)':
   prog.cpp:76:42: error: no match for 'operator[]' (operand types are 
          'std::vector<cell>' and 'cell')
     {q.push(cell(x, y, t.dis + 1));parent[cell(x, y, t.dis + 1)]=t;}

我在代码中注释了第76行。

  struct cell {
      int x, y;
      int dis;
      cell() {}
      cell(int x, int y, int dis): x(x), y(y), dis(dis) {}
  };
   //cell parent[10000];
  typedef cell c;
  vector<c> parent(10000);
  bool isInside(int x, int y, int N) {
      if (x >= 1 && x <= N && y >= 1 && y <= N)
          return true;
      return false;
  }

  int minStepToReachTarget(int knightPos[], int targetPos[], int N) {
      // x and y direction, where a knight can move
      int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
      int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
      // queue for storing states of knight in board
      queue<cell> q;
      // push starting position of knight with 0 distance
      q.push(cell(knightPos[0], knightPos[1], 0));
      cell t;
      int x, y;
      bool visit[N + 1][N + 1];
      // make all cell unvisited
      for (int i = 1; i <= N; i++)
          for (int j = 1; j <= N; j++)
              visit[i][j] = false;
      visit[knightPos[0]][knightPos[1]] = true;
      //    parent[cell(knightPos[0], knightPos[1], 0)]=t;
      // loop untill we have one element in queue
      while (!q.empty()) {
          t = q.front();
          //parent[t]=t;
          q.pop();
          visit[t.x][t.y] = true;
          // if current cell is equal to target cell,
          // return its distance
          if (t.x == targetPos[0] && t.y == targetPos[1])
              return t.dis;
          // loop for all reahable states
          for (int i = 0; i < 8; i++) {
              x = t.x + dx[i];
              y = t.y + dy[i];
              // If rechable state is not yet visited and
              // inside board, push that state into queue
              if (isInside(x, y, N) && !visit[x][y]) {
                  q.push(cell(x, y, t.dis + 1));
                  //76 ERROR: parent[cell(x, y, t.dis + 1)]=t;}
              }
          }
      }

      int main() {
          // size of square board
          int N = 6;
          int knightPos[] = {4, 5};
          int targetPos[] = {1, 1};
          int m= minStepToReachTarget(knightPos, targetPos, N);
          cout<<m<<endl;
          return 0;
      }
c++ breadth-first-search
1个回答
0
投票

#码

    int dx[8] = {-1,-2, 1 ,2 ,-1, -2, 1, 2};
    int dy[8] = {-2,-1, -2,-1, 2, 1, 2, 1};
    q.push(ppi(pi(kx, ky), 0));
    while(!q.empty()){
      pi cur = q.front().first; int d = q.front().second; q.pop();
      int x = cur.first;
      int y = cur.second;
      // printf("%d %d %d\n", x,y, visited[x][y]);
      if(visited[x][y]) continue;
      visited[x][y] = true;
      if (x == tx && y == ty){
        printf("%d", d);
        return 0;
      }
      for(int i = 0; i<8; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx <= 0 || nx > n || ny <= 0 || ny > n) continue;
        q.push(ppi(pi(nx, ny), d+1));
      }
    }
    printf("-1");

Explanation

这是我实现的bfs。我将网格存储为布尔值,我可以跟踪我已经走过的方格。如果我无法到达广场,我输出-1。我还建议不要使用函数调用,除非真的有必要,因为这是一个简单的BFS问题。

Extension

为了防止你想要了解更多信息,我从我的代码中获取了以下数据块以解决更难的问题,其中存在一个带有禁用方块的网格,骑士无法行进。在这种情况下,禁止的方块最初被标记为“真”而不是“假”,以表示已经旅行,所以我不会继续它。

我希望我的上述解决方案有所帮

© www.soinside.com 2019 - 2024. All rights reserved.