/*
Author: SJ
*/
#include<bits/stdc++.h>
const int N = 1000 + 10;
using ll = long long;
using ull = unsigned long long;
/*这个问题显然能建出无向图用最短路求解, 然后观察得知
图中边权只有0, 1两种.用0-1bfs求解将时间复杂度从O(mlogm)
降为O(|E|), 在这题也就是O(rc);
*/
/*
写代码一定要优美
*/
int t, r, c, dis[N][N];
bool vis[N][N];
char g[N][N];
std::string check = "\\/\\/";
int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1};
int dx2[] = {-1, -1, 0, 0}, dy2[] = {-1, 0, 0, -1};
struct st {
int x, y;
};
std::deque<st> dq;
void init() {
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
std::cin >> g[i][j];
}
void bfs() {
dq.push_front({1, 1});
vis[1][1] = 1;
dis[1][1] = 0;
while (!dq.empty()) {
st tmp = dq.front();
int x1 = tmp.x, y1 = tmp.y;
dq.pop_front();
vis[x1][y1] = 1;
// std::cout << x1 << ' ' << y1 << "\n";
for (int i = 0; i < 4; i++) {
int x2 = x1 + dx[i], y2 = y1 + dy[i], x3 = x1 + dx2[i], y3 = y1 + dy2[i];
// std::cout << x2 << ' ' << y2 << ' ' << x3 << ' ' << y3 << "\n";
if (x2 < 1 || x2 > r + 1 || y2 < 1 || y2 > c + 1) continue;
if (vis[x2][y2]) continue;
int w = 0 + (g[x3][y3] != check[i]);
// std::cout << x2 << ' ' << y2 << ' ' << x3 << ' ' << y3 << ' ' << g[x3][y3] << ' ' << check[i] << ' ' << w << "\n";
if (dis[x2][y2] > dis[x1][y1] + w) {
dis[x2][y2] = dis[x1][y1] + w;
if (!w) dq.push_front({x2, y2});
else dq.push_back({x2, y2});
}
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
// std::cin >> t;
// while (t--) {
std::cin >> r >> c;
init();
if ((r + c) % 2 != 0) {
std::cout << "NO SOLUTION" << "\n";
// continue;
}
bfs();
std::cout << dis[r + 1][c + 1] << "\n";
// }
return 0;
}
想求一下3号点的数据