c++ - 创建表示二维矩阵中所有可能路径的图形

Question

我正在尝试生成一个表示矩阵中所有可能路径的图形。

• 可能的路径包括:上、下、左、右。
• 我的算法遍历矩阵，但我意识到这行不通。
• 虽然欢迎提供代码，但也欢迎提出想法或建议。我一直在查看在线资源，但未能找到我能够理解的针对此特定问题的示例解决方案。
• 我的代码应该按原样运行，尽管它当然有缺陷:)

C++

#include <stdlib.h>
#include <stdio.h>
#include <vector>

struct Tile
{
    int tileId;
    int moveCost;
};

class Node
{

public:

    Node();

    void setTile(Tile *tile);
    void addLink(Node *node);

private:
    std::vector<Node *> mLinks;
    Tile *mTile;
};

Node::Node()
{

}

void Node::setTile(Tile *tile)
{
    mTile = tile;
}

void Node::addLink(Node *node)
{
    mLinks.push_back(node);
}



int main()
{
    int boardSize = 5;

    std::vector< std::vector<Tile *> > board;
    board.resize(boardSize, std::vector<Tile *>(boardSize, NULL));

    // generate the board
    int i = 0;
    for (int x = 0; x < boardSize; x++)
    {
        for (int y = 0; y < boardSize; y++)
        {
            int mc = 1;
            if (i == 7 || i == 8 || i == 12 || i == 17 || i == 18)
            {
                mc = 9;
            }
            Tile *tile = new Tile();
            tile->tileId = i;
            tile->moveCost = mc;
            board[x][y] = tile;
            i++;
        }
    }

    // create graph from the board, with each node having a link to it's nieghboring tile
    Node *rootNode = new Node(); // only serves as the entry point
    for (int x = 0; x < boardSize; x++)
    {
        for (int y = 0; y < boardSize; y++)
        {
            // this tile node
            Node *thisNode = new Node();
            thisNode->setTile(board[x][y]);

            // up neighbor node
            if (y - 1 >= 0)
            {
                Node *upNode = new Node();
                upNode->setTile(board[x][y - 1]);
                thisNode->addLink(upNode);
            }

            // down neighbor node
            if (y + 1 < boardSize)
            {
                Node *downNode = new Node();
                downNode->setTile(board[x][y + 1]);
                thisNode->addLink(downNode);
            }

            // left neighbor node
            if (x - 1 >= 0)
            {
                Node *leftNode = new Node();
                leftNode->setTile(board[x - 1][y]);
                thisNode->addLink(leftNode);
            }

            // right neighbor node
            if (x + 1 < boardSize)
            {
                Node *rightNode = new Node();
                rightNode->setTile(board[x + 1][y]);
                thisNode->addLink(rightNode);

            }

            // only add the first node to the rootNode
            if (x + y == 0)
            {
                rootNode->addLink(thisNode);
            }
        }
    }
}

编辑:例如，给定矩阵的这种可视化:

[0][1][2][3][4]
[5][6][7][8][9]
[10][11][12][13][14]
[15][16][17][18][19]
[20][21][22][23][24]

我希望每个图形节点都包含指向它的每个邻居(上、下、左、右)的指针列表

Tile 0 neighbors: 1,5
Tile 1 neighbors: 0,6,2
Tile 2 neighbors: 1,7,3

等等

Answer 1

代码中的注释:

struct MatrixPos {
  uint row;
  uint col;
};

std::ostream& operator << (std::ostream& o, const MatrixPos& p) {
  o << "[" << p.row << "," << p.col << "]";
  return o;
}

// visit the (tile.row +/- 1) and (tile.col +/- 1)
// if not out-of-bounds, collect the visited in the neighbours param
void collectNeighbours(
   uint numRows, uint numCols,
   const MatrixPos& tile,
   std::vector<MatrixPos>& dest
) {
  uint nRow=tile.row-1;
  uint nCol=tile.col;
  if(nRow<numRows) { // otherwise an underflow occurred, so not a neighbour
    dest.push_back({nRow, nCol});
  }
  nRow=tile.row+1;
  if(nRow<numRows) dest.push_back({nRow, nCol});
  nRow=tile.row;
  nCol=tile.col-1;
  if(nCol<numCols) dest.push_back({nRow, nCol});
  nCol=tile.col+1;
  if(nCol<numCols) dest.push_back({nRow, nCol});
}

// convert from {tile.row, tile.col} to linear index
uint tileIndex(const MatrixPos& tile, uint numRows) {
  return numRows*tile.row+tile.col;
}

// convert a linear index to {tile.row, tile.col}
MatrixPos tilePos(uint tileIndex, uint numRows) {
  return { tileIndex / numRows, tileIndex % numRows };
}

int main() {
  const uint numRows=5, numCols=5;
  std::vector<MatrixPos> neighbours;
  for(uint i=0; i<numRows*numCols; i++) {
    neighbours.clear();
    MatrixPos pos=tilePos(i, numRows);
    collectNeighbours(numRows, numCols, pos, neighbours);
    std::cout << "Tile " << tileIndex(pos, numRows) << " " << pos << " neighbors: ";

    // if you need so, convert each {pos->neighbour} into a node
    // a Node structure

    bool notFirst=false;
    for(auto n : neighbours) {
      if(notFirst) {
        std::cout << ",";
      }
      notFirst=true;
      std::cout << tileIndex(n, numRows);
    }
    std::cout << std::endl;
  }
}

结果:

Tile 0 [0,0] neighbors: 5,1
Tile 1 [0,1] neighbors: 6,0,2
Tile 2 [0,2] neighbors: 7,1,3
Tile 3 [0,3] neighbors: 8,2,4
Tile 4 [0,4] neighbors: 9,3
Tile 5 [1,0] neighbors: 0,10,6
Tile 6 [1,1] neighbors: 1,11,5,7
Tile 7 [1,2] neighbors: 2,12,6,8
Tile 8 [1,3] neighbors: 3,13,7,9
Tile 9 [1,4] neighbors: 4,14,8
Tile 10 [2,0] neighbors: 5,15,11
Tile 11 [2,1] neighbors: 6,16,10,12
Tile 12 [2,2] neighbors: 7,17,11,13
Tile 13 [2,3] neighbors: 8,18,12,14
Tile 14 [2,4] neighbors: 9,19,13
Tile 15 [3,0] neighbors: 10,20,16
Tile 16 [3,1] neighbors: 11,21,15,17
Tile 17 [3,2] neighbors: 12,22,16,18
Tile 18 [3,3] neighbors: 13,23,17,19
Tile 19 [3,4] neighbors: 14,24,18
Tile 20 [4,0] neighbors: 15,21
Tile 21 [4,1] neighbors: 16,20,22
Tile 22 [4,2] neighbors: 17,21,23
Tile 23 [4,3] neighbors: 18,22,24
Tile 24 [4,4] neighbors: 19,23