Блог

Я пытаюсь сгенерировать график, представляющий все возможные пути из матрицы.

• Возможные пути включают в себя: вверх, вниз, влево, вправо.
• Мой алгоритм пересекает матрицу, но я понял, что это не сработает.
• Хотя код приветствуется, даже идеи или предложения приветствуются. Я просматривал онлайн-ресурсы, но не смог найти примерное решение для этой конкретной проблемы, которое я могу понять.
• Мой код должен выполняться как есть, хотя, конечно, он ошибочен 🙂

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
  

И так далее

Комментарии в коде:

 struct MatrixPos {
  uint row;
  uint col;
};

std::ostreamamp; operator << (std::ostreamamp; o, const MatrixPosamp; 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 MatrixPosamp; tile,
   std::vector<MatrixPos>amp; 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 MatrixPosamp; 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