布线问题

bool FindPath(Position start, Position finish, int& PathLen, Position* &path) {
    if ((start.row == finish.row) && (start.col == finish.col)) {
        PathLen = 0;
        return true;
    }
    for (int i = 0; i <= m + 1; i++) {
        grid[0][i] = grid[n + 1][i] = 1;
    }
    for (int i = 0; i <= n + 1; i++) {
        grid[i][0] = grid[i][m + 1] = 1;
    }
    Position offset[4];
    offset[0].row = 0; offset[0].col = 1;
    offset[1].row = 1; offset[1].col = 0;
    offset[2].row = 0; offset[2].col = -1;
    offset[3].row = -1; offset[3].col = 0;
    int NumOfNbrs = 4;
    Position here, nbr;
    here.row = start.row; here.col = start.col;
    grid[start.row][start.col] = 2;
    LinkedQueue<Position> Q;
    do {
        for (int i = 0; i < NumOfNbrs; i++) {
            nbr.row = here.row + offset[i].row;
            nbr.col = here.col + offset[i].col;
            if (grid[nbr.row][nbr.col] == 0) {
                grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1;
                if ((nbr.row == finish.row) && (nbr.col == finish.col)) {
                    break;
                }
                Q.Add(nbr);
            }
        }
        if ((nbr.row == finish.row) && (nbr.col == finish.col)) {
            break;
        }
        if (Q.IsEmpty()) {
            return false;
        }
        Q.Delete(here);
    } while (true);
    PathLen = grid[finish.row][finish.col] - 2;
    path = new Position[PathLen];
    here = finish;
    for (int j = PathLen - 1; j >= 0; j--) {
        path[j] = here;
        for (int i = 0; i < NumOfNbrs; i++) {
            nbr.row = here.row + offset[i].row;
            nbr.col = here.col + offset[i].col;
            if (grid[nbr.row][nbr.col] == j + 2) {
                break;
            }
        }
        here = nbr;
    }
    return true;
}

最后更新: 2024年1月14日 20:14:02
创建日期: 2024年1月2日 19:47:42
回到页面顶部