Graph类
class Graph {
public:
explicit Graph(int rows, int cols) : mat(rows, vector<int8_t>(cols, false)) {}
void push(int row0, int col0, bool path) { mat[row0][col0] = path; }
int minSteps(int row0, int col0, int row1, int col1) const {
if (mat.empty() || mat[0].empty()) {
return -1;
}
const int rows = static_cast<int>(mat.size());
const int cols = static_cast<int>(mat[0].size());
if (!check(row0, col0) || !check(row1, col1) || !mat[row0][col0] || !mat[row1][col1]) {
return -1;
}
const int directSize = 4, directX[] = {0, 0, -1, 1}, directY[] = {-1, 1, 0, 0};
queue<tuple<int, int, int>> queue0;
queue0.push(make_tuple(row0, col0, 0));
vector<vector<int8_t>> visited(rows, vector<int8_t>(cols, false));
visited[row0][col0] = true;
while (!queue0.empty()) {
int row2, col2, step2;
tie(row2, col2, step2) = queue0.front();
queue0.pop();
const int step3 = step2 + 1;
for (int i = 0; i < directSize; ++i) {
const int row3 = row2 + directY[i], col3 = col2 + directX[i];
if (!check(row3, col3) || !mat[row3][col3] || visited[row3][col3]) {
continue;
}
if (row3 == row1 && col3 == col1) {
return step3;
}
queue0.push(make_tuple(row3, col3, step3));
visited[row3][col3] = true;
}
}
return -1;
}
private:
inline bool check(int row0, int col0) const {
const int rows = static_cast<int>(mat.size());
const int cols = static_cast<int>(mat[0].size());
return row0 >= 0 && row0 < rows && col0 >= 0 && col0 < cols;
}
vector<vector<int8_t>> mat;
};
main函数
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
int main(void) {
int n, m, x;
scanf("%d%d", &n, &m);
Graph graph(n, m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%d", &x);
graph.push(i, j, !x);
}
}
const int step = graph.minSteps(0, 0, n - 1, m - 1);
printf("%d\n", step);
return 0;
}