机器人在网格上移动的最短路径

Question

我的赋值有问题。我写了一个代码，但它在一些输入中给出了错误的答案(我看不到输入(。然而，代码对我尝试的所有示例都很好。

问题来了。

机器人将邮件发送到X的各个角落。国家X可以表示为一个N×M字段，其中的每个单元格要么可交叉(表示为'.'(，要么不可交叉('#'(。机器人只能从当前单元格移动到相邻单元格。机器人还需要转弯，例如，如果机器人向右走，他需要向上移动，他首先向左转弯。同样，它也可以向右转弯。机器人的开发者还提供了在与当前方向相反的方向上的转弯。在计算最短路径时没有考虑转弯，因为机器人很容易完成转弯。由于故障，机器人在左转后，在右转之前无法再左转，反之亦然。转弯本身是独立进行的，不影响这一规则，然而，机器人在同一个单元中不能进行一次以上的转弯。你被指派为机器人编写一个修改后的程序，这样它就可以计算出这个小故障的最短路径。

输入示例：

5 5 // N and M
#...# // grid
..#.#
..#.#
..#.#
#....
2 2 // source
2 4 // destination

输出应该包括最短路径的长度和最短路径本身(如果没有最短路径，则仅为"-1"(。保证来源和目的地都可以通过。在迈出第一步之前，您可以将机器人转向任何方向。

以下是我所做的。我计算了每个单元格有12个节点的图(方向(上/下/左/右(和可用移动(左/右/两者(的每个组合都有一个节点(。使用堆栈实现BFS(起初堆栈中有两个顶点，一个用于源(向上+两者(，一个(向左+两者((。如果BFS到达与目的地对应的12个节点中的一个，则BFS停止。

我的代码：

#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
#include <utility>

class Graph {
public:
std::vector<std::vector<int>> adjacent_;
int number_of_vertices_;
explicit Graph(int number_of_vertices);
void AddEdge(int first_vertex, int second_vertex) {
adjacent_[first_vertex].emplace_back(second_vertex);
}
};

Graph::Graph(int number_of_vertices) {
number_of_vertices_ = number_of_vertices;
std::vector<std::vector<int>> adjacent(number_of_vertices);
adjacent_ = adjacent;
}

enum Looks { UP = 0, DOWN = 3, LEFT = 6, RIGHT = 9 };

enum Moves { L = 0, R = 1, LR = 2 };

void MovesRight(int row, int column, int number_of_columns, Graph &map) {
int rows_in_map = 12 * row;
map.AddEdge((rows_in_map + UP + R) * number_of_columns + column,
(rows_in_map + RIGHT + L) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + UP + LR) * number_of_columns + column,
(rows_in_map + RIGHT + L) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + RIGHT + R) * number_of_columns + column,
(rows_in_map + RIGHT + R) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + RIGHT + LR) * number_of_columns + column,
(rows_in_map + RIGHT + LR) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + RIGHT + L) * number_of_columns + column,
(rows_in_map + RIGHT + L) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + LEFT + R) * number_of_columns + column,
(rows_in_map + RIGHT + R) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + LEFT + LR) * number_of_columns + column,
(rows_in_map + RIGHT + LR) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + LEFT + L) * number_of_columns + column,
(rows_in_map + RIGHT + L) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + DOWN + L) * number_of_columns + column,
(rows_in_map + RIGHT + R) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + DOWN + LR) * number_of_columns + column,
(rows_in_map + RIGHT + R) * number_of_columns + column + 1);
}

void MovesLeft(int row, int column, int number_of_columns, Graph &map) {
int rows_in_map = 12 * row;
map.AddEdge((rows_in_map + UP + L) * number_of_columns + column,
(rows_in_map + LEFT + R) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + UP + LR) * number_of_columns + column,
(rows_in_map + LEFT + R) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + RIGHT + R) * number_of_columns + column,
(rows_in_map + LEFT + R) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + RIGHT + LR) * number_of_columns + column,
(rows_in_map + LEFT + LR) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + RIGHT + L) * number_of_columns + column,
(rows_in_map + LEFT + L) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + LEFT + R) * number_of_columns + column,
(rows_in_map + LEFT + R) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + LEFT + LR) * number_of_columns + column,
(rows_in_map + LEFT + LR) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + LEFT + L) * number_of_columns + column,
(rows_in_map + LEFT + L) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + DOWN + R) * number_of_columns + column,
(rows_in_map + RIGHT + L) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + DOWN + LR) * number_of_columns + column,
(rows_in_map + RIGHT + L) * number_of_columns + column - 1);
}

void MovesUp(int row, int column, int number_of_columns, Graph &map) {
int rows_in_map = 12 * row;
map.AddEdge((rows_in_map + UP + L) * number_of_columns + column,
(rows_in_map - 12 + UP + L) * number_of_columns + column);
map.AddEdge((rows_in_map + UP + LR) * number_of_columns + column,
(rows_in_map - 12 + UP + LR) * number_of_columns + column);
map.AddEdge((rows_in_map + UP + R) * number_of_columns + column,
(rows_in_map - 12 + UP + R) * number_of_columns + column);
map.AddEdge((rows_in_map + RIGHT + L) * number_of_columns + column,
(rows_in_map - 12 + UP + R) * number_of_columns + column);
map.AddEdge((rows_in_map + RIGHT + LR) * number_of_columns + column,
(rows_in_map - 12 + UP + R) * number_of_columns + column);
map.AddEdge((rows_in_map + LEFT + R) * number_of_columns + column,
(rows_in_map - 12 + UP + L) * number_of_columns + column);
map.AddEdge((rows_in_map + LEFT + LR) * number_of_columns + column,
(rows_in_map - 12 + UP + L) * number_of_columns + column);
map.AddEdge((rows_in_map + DOWN + L) * number_of_columns + column,
(rows_in_map - 12 + UP + L) * number_of_columns + column);
map.AddEdge((rows_in_map + DOWN + LR) * number_of_columns + column,
(rows_in_map - 12 + UP + LR) * number_of_columns + column);
map.AddEdge((rows_in_map + DOWN + R) * number_of_columns + column,
(rows_in_map - 12 + UP + R) * number_of_columns + column);
}

void MovesDown(int row, int column, int number_of_columns, Graph &map) {
int rows_in_map = 12 * row;
map.AddEdge((rows_in_map + UP + L) * number_of_columns + column,
(rows_in_map  + 12 + DOWN + L) * number_of_columns + column);
map.AddEdge((rows_in_map + UP + LR) * number_of_columns + column,
(rows_in_map + 12 + DOWN + LR) * number_of_columns + column);
map.AddEdge((rows_in_map + UP + R) * number_of_columns + column,
(rows_in_map + 12 + DOWN + R) * number_of_columns + column);
map.AddEdge((rows_in_map + RIGHT + R) * number_of_columns + column,
(rows_in_map + 12 + DOWN + L) * number_of_columns + column);
map.AddEdge((rows_in_map + RIGHT + LR) * number_of_columns + column,
(rows_in_map + 12 + DOWN + L) * number_of_columns + column);
map.AddEdge((rows_in_map + LEFT + L) * number_of_columns + column,
(rows_in_map + 12 + DOWN + R) * number_of_columns + column);
map.AddEdge((rows_in_map + LEFT + LR) * number_of_columns + column,
(rows_in_map + 12 + DOWN + R) * number_of_columns + column);
map.AddEdge((rows_in_map + DOWN + L) * number_of_columns + column,
(rows_in_map + 12 + DOWN + L) * number_of_columns + column);
map.AddEdge((rows_in_map + DOWN + LR) * number_of_columns + column,
(rows_in_map + 12 + DOWN + LR) * number_of_columns + column);
map.AddEdge((rows_in_map + DOWN + R) * number_of_columns + column,
(rows_in_map + 12 + DOWN + R) * number_of_columns + column);
}

void MakeGraph(int number_of_rows, int number_of_columns,
std::vector<std::vector<char>> &grid, Graph &map) {
for (int row = 0; row < number_of_rows; ++row) {
for (int column = 0; column < number_of_columns; ++column) {
std::cin >> grid[row][column];
}
}
for (int row = 0; row < number_of_rows; ++row) {
for (int column = 0; column < number_of_columns; ++column) {
if (column + 1 < number_of_columns) {
if (grid[row][column] == '.' && grid[row][column + 1] == '.') {
MovesRight(row, column, number_of_columns, map);
}
}
if (0 < column) {
if (grid[row][column] == '.' && grid[row][column - 1] == '.') {
MovesLeft(row, column, number_of_columns, map);
}
}
if (0 < row) {
if (grid[row][column] == '.' && grid[row - 1][column] == '.') {
MovesUp(row, column, number_of_columns, map);
}
}
if (row + 1 < number_of_rows) {
if (grid[row][column] == '.' && grid[row + 1][column] == '.') {
MovesDown(row, column, number_of_columns, map);
}
}
}
}
}

int BFS(Graph &map, int source, int destination,
std::vector<int> &predecessor, std::vector<int> &distance,
int number_of_columns) {
std::list<int> queue;
std::vector<bool> visited(map.number_of_vertices_, false);
visited[source + (UP + LR) * number_of_columns] = true;
distance[source + (UP + LR) * number_of_columns] = 0;
queue.push_back(source + (UP + LR) * number_of_columns);
visited[source + (LEFT + LR) * number_of_columns] = true;
distance[source + (LEFT + LR) * number_of_columns] = 0;
queue.push_back(source + (LEFT + LR) * number_of_columns);
while (!queue.empty()) {
int vertex;
vertex = queue.front();
queue.pop_front();

for (size_t counter = 0; counter < map.adjacent_[vertex].size(); ++counter) {
int current_vertex = map.adjacent_[vertex][counter];
if (!visited[current_vertex]) {
visited[current_vertex] = true;
distance[current_vertex] = distance[vertex] + 1;
predecessor[current_vertex] = vertex;
queue.push_back(current_vertex);
if ((current_vertex / (12 * number_of_columns)) * (12 * number_of_columns)
+ (current_vertex % number_of_columns) == destination) {
return current_vertex;
}
}
}
}
return -1;
}

void printShortestDistance(Graph &map, int source,
int destination, int number_of_columns) {
std::vector<int> predecessor(map.number_of_vertices_, -1);
std::vector<int> distance(map.number_of_vertices_, 10000000);

int result = BFS(map, source, destination, predecessor, distance,
number_of_columns);
if (result == -1) {
std::cout << -1 << "n";
} else {
std::cout << distance[result] << "n";
int current_vertex = result;
std::vector<std::pair<int, int>> path;
while (current_vertex != -1) {
path.emplace_back(((current_vertex / number_of_columns) / 12) + 1,
(current_vertex % number_of_columns) + 1);
current_vertex = predecessor[current_vertex];
}
for (size_t i = 0; i < path.size(); ++i) {
std::cout << path[path.size() - 1 - i].first << " "<<
path[path.size() - 1 - i].second << "n";
}
}
}

int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int number_of_rows, number_of_columns;
std::cin >> number_of_rows >> number_of_columns;
std::vector<std::vector<char>> grid(number_of_rows,
std::vector<char>(number_of_columns));
Graph map(12 * number_of_rows * number_of_columns);
MakeGraph(number_of_rows, number_of_columns, grid, map);
int first_row, second_row, first_column, second_column;
std::cin >> first_row >> first_column >> second_row >> second_column;
--first_row;
--first_column;
--second_row;
--second_column;
int source = 12 * first_row * number_of_columns + first_column;
int destination = 12 * second_row * number_of_columns + second_column;
printShortestDistance(map, source, destination, number_of_columns);

return 0;
}

你能告诉我我的实现中出了什么问题吗？或者给出一些可能失败的输入的想法吗？

Answer 1

此映射在x时失败，一个更精简的映射可能会更容易查看。来源在上方，左侧，目的地在下方，右侧。

Seed: 3499211612
...#..
#..#.#
..##.#
.#..#.
x.....
#..#..
***...
.**...
**....
*.....
*.....
......

由于这些节点有一个将其视为前置节点的节点(由于您的图，有些节点可能会被访问更多次。

用于测试的代码

#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
#include <utility>
using GridType = std::vector<std::vector<char>>;
constexpr char empty { '.' };
constexpr char block { '#' };
class Graph {
public:
std::vector<std::vector<int>> adjacent_;
int number_of_vertices_;
explicit Graph(int number_of_vertices);
void AddEdge(int first_vertex, int second_vertex) {
adjacent_[first_vertex].emplace_back(second_vertex);
}
};

Graph::Graph(int number_of_vertices) {
number_of_vertices_ = number_of_vertices;
std::vector<std::vector<int>> adjacent(number_of_vertices);
adjacent_ = adjacent;
}

enum Looks { UP = 0, DOWN = 3, LEFT = 6, RIGHT = 9 };

enum Moves { L = 0, R = 1, LR = 2 };

void MovesRight(int row, int column, int number_of_columns, Graph &map) {
int rows_in_map = 12 * row;
map.AddEdge((rows_in_map + UP + R) * number_of_columns + column,
(rows_in_map + RIGHT + L) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + UP + LR) * number_of_columns + column,
(rows_in_map + RIGHT + L) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + RIGHT + R) * number_of_columns + column,
(rows_in_map + RIGHT + R) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + RIGHT + LR) * number_of_columns + column,
(rows_in_map + RIGHT + LR) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + RIGHT + L) * number_of_columns + column,
(rows_in_map + RIGHT + L) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + LEFT + R) * number_of_columns + column,
(rows_in_map + RIGHT + R) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + LEFT + LR) * number_of_columns + column,
(rows_in_map + RIGHT + LR) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + LEFT + L) * number_of_columns + column,
(rows_in_map + RIGHT + L) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + DOWN + L) * number_of_columns + column,
(rows_in_map + RIGHT + R) * number_of_columns + column + 1);
map.AddEdge((rows_in_map + DOWN + LR) * number_of_columns + column,
(rows_in_map + RIGHT + R) * number_of_columns + column + 1);
}

void MovesLeft(int row, int column, int number_of_columns, Graph &map) {
int rows_in_map = 12 * row;
map.AddEdge((rows_in_map + UP + L) * number_of_columns + column,
(rows_in_map + LEFT + R) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + UP + LR) * number_of_columns + column,
(rows_in_map + LEFT + R) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + RIGHT + R) * number_of_columns + column,
(rows_in_map + LEFT + R) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + RIGHT + LR) * number_of_columns + column,
(rows_in_map + LEFT + LR) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + RIGHT + L) * number_of_columns + column,
(rows_in_map + LEFT + L) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + LEFT + R) * number_of_columns + column,
(rows_in_map + LEFT + R) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + LEFT + LR) * number_of_columns + column,
(rows_in_map + LEFT + LR) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + LEFT + L) * number_of_columns + column,
(rows_in_map + LEFT + L) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + DOWN + R) * number_of_columns + column,
(rows_in_map + RIGHT + L) * number_of_columns + column - 1);
map.AddEdge((rows_in_map + DOWN + LR) * number_of_columns + column,
(rows_in_map + RIGHT + L) * number_of_columns + column - 1);
}

void MovesUp(int row, int column, int number_of_columns, Graph &map) {
int rows_in_map = 12 * row;
map.AddEdge((rows_in_map + UP + L) * number_of_columns + column,
(rows_in_map - 12 + UP + L) * number_of_columns + column);
map.AddEdge((rows_in_map + UP + LR) * number_of_columns + column,
(rows_in_map - 12 + UP + LR) * number_of_columns + column);
map.AddEdge((rows_in_map + UP + R) * number_of_columns + column,
(rows_in_map - 12 + UP + R) * number_of_columns + column);
map.AddEdge((rows_in_map + RIGHT + L) * number_of_columns + column,
(rows_in_map - 12 + UP + R) * number_of_columns + column);
map.AddEdge((rows_in_map + RIGHT + LR) * number_of_columns + column,
(rows_in_map - 12 + UP + R) * number_of_columns + column);
map.AddEdge((rows_in_map + LEFT + R) * number_of_columns + column,
(rows_in_map - 12 + UP + L) * number_of_columns + column);
map.AddEdge((rows_in_map + LEFT + LR) * number_of_columns + column,
(rows_in_map - 12 + UP + L) * number_of_columns + column);
map.AddEdge((rows_in_map + DOWN + L) * number_of_columns + column,
(rows_in_map - 12 + UP + L) * number_of_columns + column);
map.AddEdge((rows_in_map + DOWN + LR) * number_of_columns + column,
(rows_in_map - 12 + UP + LR) * number_of_columns + column);
map.AddEdge((rows_in_map + DOWN + R) * number_of_columns + column,
(rows_in_map - 12 + UP + R) * number_of_columns + column);
}

void MovesDown(int row, int column, int number_of_columns, Graph &map) {
int rows_in_map = 12 * row;
map.AddEdge((rows_in_map + UP + L) * number_of_columns + column,
(rows_in_map  + 12 + DOWN + L) * number_of_columns + column);
map.AddEdge((rows_in_map + UP + LR) * number_of_columns + column,
(rows_in_map + 12 + DOWN + LR) * number_of_columns + column);
map.AddEdge((rows_in_map + UP + R) * number_of_columns + column,
(rows_in_map + 12 + DOWN + R) * number_of_columns + column);
map.AddEdge((rows_in_map + RIGHT + R) * number_of_columns + column,
(rows_in_map + 12 + DOWN + L) * number_of_columns + column);
map.AddEdge((rows_in_map + RIGHT + LR) * number_of_columns + column,
(rows_in_map + 12 + DOWN + L) * number_of_columns + column);
map.AddEdge((rows_in_map + LEFT + L) * number_of_columns + column,
(rows_in_map + 12 + DOWN + R) * number_of_columns + column);
map.AddEdge((rows_in_map + LEFT + LR) * number_of_columns + column,
(rows_in_map + 12 + DOWN + R) * number_of_columns + column);
map.AddEdge((rows_in_map + DOWN + L) * number_of_columns + column,
(rows_in_map + 12 + DOWN + L) * number_of_columns + column);
map.AddEdge((rows_in_map + DOWN + LR) * number_of_columns + column,
(rows_in_map + 12 + DOWN + LR) * number_of_columns + column);
map.AddEdge((rows_in_map + DOWN + R) * number_of_columns + column,
(rows_in_map + 12 + DOWN + R) * number_of_columns + column);
}

void FillGraph(int number_of_rows, int number_of_columns,
std::vector<std::vector<char>> &grid, Graph &map) {
for (int row = 0; row < number_of_rows; ++row) {
for (int column = 0; column < number_of_columns; ++column) {
if (column + 1 < number_of_columns) {
if (grid[row][column] == '.' && grid[row][column + 1] == '.') {
MovesRight(row, column, number_of_columns, map);
}
}
if (0 < column) {
if (grid[row][column] == '.' && grid[row][column - 1] == '.') {
MovesLeft(row, column, number_of_columns, map);
}
}
if (0 < row) {
if (grid[row][column] == '.' && grid[row - 1][column] == '.') {
MovesUp(row, column, number_of_columns, map);
}
}
if (row + 1 < number_of_rows) {
if (grid[row][column] == '.' && grid[row + 1][column] == '.') {
MovesDown(row, column, number_of_columns, map);
}
}
}
}
}
void MakeGraph(int number_of_rows, int number_of_columns,
std::vector<std::vector<char>> &grid, Graph &map) {
for (int row = 0; row < number_of_rows; ++row) {
for (int column = 0; column < number_of_columns; ++column) {
std::cin >> grid[row][column];
}
}
FillGraph(number_of_rows, number_of_columns, grid, map);
}

int BFS(Graph &map, int source, int destination,
std::vector<int> &predecessor, std::vector<int> &distance,
int number_of_columns) {
std::list<int> queue;
std::vector<bool> visited(map.number_of_vertices_, false);
visited[source + (UP + LR) * number_of_columns] = true;
distance[source + (UP + LR) * number_of_columns] = 0;
queue.push_back(source + (UP + LR) * number_of_columns);
visited[source + (LEFT + LR) * number_of_columns] = true;
distance[source + (LEFT + LR) * number_of_columns] = 0;
queue.push_back(source + (LEFT + LR) * number_of_columns);
int vertex = 0;
while (!queue.empty()) {
vertex = queue.front();
queue.pop_front();
for (size_t counter = 0; counter < map.adjacent_[vertex].size(); ++counter) {
int current_vertex = map.adjacent_[vertex][counter];
if (!visited[current_vertex]) {
visited[current_vertex] = true;
distance[current_vertex] = distance[vertex] + 1;
predecessor[current_vertex] = vertex;
queue.push_back(current_vertex);
if ((current_vertex / (12 * number_of_columns)) * (12 * number_of_columns)
+ (current_vertex % number_of_columns) == destination) {
return current_vertex;
}
}
}
}
return -vertex;
}
void PrintGrid(std::vector<std::vector<char>>& grid) {
for(auto& row : grid) {
for(auto& pos : row) {
std::cout << pos;
}
std::cout << 'n';
}
}

int printShortestDistance(Graph &map, int source,
int destination, int number_of_columns,
bool showMap = false) {
std::vector<int> predecessor(map.number_of_vertices_, -1);
std::vector<int> distance(map.number_of_vertices_, 10000000);
int result = BFS(map, source, destination, predecessor, distance,
number_of_columns);
if (showMap) {
GridType grid(number_of_columns, std::vector<char>(number_of_columns, empty));
for(auto pred : predecessor) {
int row = ((pred / number_of_columns) / 12);
int col = (pred % number_of_columns);
grid[row][col] = '*';
}
PrintGrid(grid);
}
if (result <= 0) {
std::cout << -1 << "n";
} else {
std::cout << distance[result] << "n";
int current_vertex = result;
std::vector<std::pair<int, int>> path;
while (current_vertex != -1) {
path.emplace_back(((current_vertex / number_of_columns) / 12) + 1,
(current_vertex % number_of_columns) + 1);
current_vertex = predecessor[current_vertex];
}
for (size_t i = 0; i < path.size(); ++i) {
std::cout << path[path.size() - 1 - i].first << " "<<
path[path.size() - 1 - i].second << "n";
}
}
return result;
}

void RunGraph(int number_of_rows, int number_of_columns, int source, int destination) {
std::vector<std::vector<char>> grid(number_of_rows,
std::vector<char>(number_of_columns));
Graph map(12 * number_of_rows * number_of_columns);
MakeGraph(number_of_rows, number_of_columns, grid, map);
printShortestDistance(map, source, destination, number_of_columns);
}
void Solve() {
int number_of_rows, number_of_columns;
std::cin >> number_of_rows >> number_of_columns;
int first_row, second_row, first_column, second_column;
std::cin >> first_row >> first_column >> second_row >> second_column;
--first_row;
--first_column;
--second_row;
--second_column;
int source = 12 * first_row * number_of_columns + first_column;
int destination = 12 * second_row * number_of_columns + second_column;
RunGraph(number_of_rows, number_of_columns, source, destination);
}
#include<random>
void Test() {
int number_of_rows = 10, number_of_columns = 10;
int source = 0;
int destination = 12 * (number_of_rows-1) * number_of_columns + (number_of_columns-1);
std::random_device rd;  //Will be used to obtain a seed for the random number engine
auto seed = rd();
std::mt19937 gen(seed); //Standard mersenne_twister_engine seeded with rd()
std::uniform_int_distribution<> distribrow(0, number_of_rows-1);
std::uniform_int_distribution<> distribcol(0, number_of_columns-1);
GridType grid(number_of_rows, std::vector<char>(number_of_columns, empty));
for (int filled = 1; filled < (number_of_rows-1) * (number_of_columns -1); ++filled ) {
int row = distribrow(gen);
int column = distribcol(gen);
while (grid[row][column] == block ||
(!row && !column) || (row == (number_of_rows-1) && column == (number_of_columns-1))) {
row = distribrow(gen);
column = distribcol(gen);
}
grid[row][column] = block;
Graph map(12 * number_of_rows * number_of_columns);
FillGraph(number_of_rows, number_of_columns, grid, map);
if (0 >= printShortestDistance(map, source, destination, number_of_columns)) {
std::cout << "Seed: " << seed << 'n';
PrintGrid(grid);
printShortestDistance(map, source, destination, number_of_columns, true);
std::cout << std::endl;
grid[row][column] = empty;
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
Test();//Solve();
return 0;
}