78 lines
2.2 KiB
C++
78 lines
2.2 KiB
C++
#include <iostream>
|
||
#include <vector>
|
||
#include <deque>
|
||
|
||
using namespace std;
|
||
|
||
// 方向数组：右上，右下，左下，左上 (对应格点的移动)
|
||
const int dir[4][2] = {{-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
|
||
// 对应方向上，方格应该有的形状
|
||
const char expect[4] = {'/', '\\', '/', '\\'};
|
||
// 对应方向上，方格在 mat 中的坐标偏移
|
||
const int dr[4] = {-1, 0, 0, -1};
|
||
const int dc[4] = {0, 0, -1, -1};
|
||
|
||
const int INF = 1e9;
|
||
|
||
int main() {
|
||
int n, m;
|
||
if (!(cin >> n >> m)) return 0;
|
||
|
||
// 奇偶性剪枝：如果终点坐标和为奇数，绝对无法到达
|
||
if ((n + m) % 2 != 0) {
|
||
cout << "NO SOLUTION" << endl;
|
||
return 0;
|
||
}
|
||
|
||
vector<vector<char>> mat(n, vector<char>(m));
|
||
// 修正：dist 必须是 int 类型，初始化为无穷大
|
||
vector<vector<int>> dist(n + 1, vector<int>(m + 1, INF));
|
||
|
||
for (int i = 0; i < n; ++i) {
|
||
for (int j = 0; j < m; ++j) {
|
||
cin >> mat[i][j];
|
||
}
|
||
}
|
||
|
||
deque<pair<int, int>> dq;
|
||
dist[0][0] = 0;
|
||
dq.push_back({0, 0});
|
||
|
||
while (!dq.empty()) {
|
||
pair<int, int> curr = dq.front();
|
||
dq.pop_front();
|
||
|
||
int r = curr.first;
|
||
int c = curr.second;
|
||
|
||
for (int i = 0; i < 4; ++i) {
|
||
int nr = r + dir[i][0];
|
||
int nc = c + dir[i][1];
|
||
|
||
// 检查格点是否越界
|
||
if (nr >= 0 && nr <= n && nc >= 0 && nc <= m) {
|
||
// 对应方格的坐标
|
||
int tr = r + dr[i];
|
||
int tc = c + dc[i];
|
||
|
||
// 如果当前方向的字符与地图不符，权值为 1，否则为 0
|
||
int weight = (mat[tr][tc] == expect[i] ? 0 : 1);
|
||
|
||
if (dist[r][c] + weight < dist[nr][nc]) {
|
||
dist[nr][nc] = dist[r][c] + weight;
|
||
if (weight == 0) {
|
||
dq.push_front({nr, nc}); // 权值为0，插到队头
|
||
} else {
|
||
dq.push_back({nr, nc}); // 权值为1，插到队尾
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
if (dist[n][m] == INF) cout << "NO SOLUTION" << endl;
|
||
else cout << dist[n][m] << endl;
|
||
|
||
return 0;
|
||
}
|