#include #include #include 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> mat(n, vector(m)); // 修正:dist 必须是 int 类型,初始化为无穷大 vector> dist(n + 1, vector(m + 1, INF)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> mat[i][j]; } } deque> dq; dist[0][0] = 0; dq.push_back({0, 0}); while (!dq.empty()) { pair 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; }