Loj 2632
题意：见上
网格图可以连边转图论问题。
这里有$(n+1)(m+1)$个点，然后一个/就连这个对角的点，费用为0。还要补充另一个对角连边，费用为1。求$1$到$(n+1)(m+1)$的最短路即可。写$0-1BFS$.
知识点：
1、0-1 BFS 写错了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
struct edge {int v, w, nxt;} ed[500000 * 2 + 5];
deque<int > q;
int n, m, en, hd[300000 + 5], dis[300000 + 5];
char s[505][505];
void ins(int u, int v, int w) {ed[++en] = (edge){v, w, hd[u]}, hd[u] = en;}
void bfs() {
for (int i = 1; i <= (n + 1) * (m + 1); ++i) dis[i] = 1000000000;
q.push_front(1), dis[1] = 0;
while (!q.empty()) {
int u = q.front(); q.pop_front();
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (dis[e.v] > dis[u] + e.w) {
dis[e.v] = dis[u] + e.w;
if (e.w == 0) q.push_front(e.v); else q.push_back(e.v);
}
}
}
}
void clean() {
en = 0, ms(hd, -1);
}
int solve() {
scanf("%d%d", &n, &m);
if ((n & 1) != (m & 1)) return printf("NO SOLUTION\n"), 0;
clean();
for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s[i][j] == '\\') {
ins((i - 1) * (m + 1) + j, i * (m + 1) + j + 1, 0);
ins(i * (m + 1) + j + 1, (i - 1) * (m + 1) + j, 0);
ins((i - 1) * (m + 1) + j + 1, i * (m + 1) + j, 1);
ins(i * (m + 1) + j, (i - 1) * (m + 1) + j + 1, 1);
} else {
ins((i - 1) * (m + 1) + j, i * (m + 1) + j + 1, 1);
ins(i * (m + 1) + j + 1, (i - 1) * (m + 1) + j, 1);
ins((i - 1) * (m + 1) + j + 1, i * (m + 1) + j, 0);
ins(i * (m + 1) + j, (i - 1) * (m + 1) + j + 1, 0);
}
}
}
/*for (int u = 1; u <= (n + 1) * (m + 1); ++u) {
cerr << u << ": ";
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
cerr << ed[i].v << "(" << ed[i].w << ") ";
}
cerr << endl;
}*/
bfs();
// for (int i = 1; i <= (n + 1) * (m + 1); ++i) cerr << "???u=" << i << ": " << dis[i] << endl;
cout << dis[(n + 1) * (m + 1)];
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
3 3
\\\
\//
\\/
*/
