每条对角线都建一条边
原来对角线有的边权为0，没有的边权为1
最短路即可
1 /************************************************************** 2 Problem: 2346 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1312 ms 7 Memory:29404 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 #include <queue> 14 15 using namespace std; 16 const int len = 505; 17 const int N = 300005; 18 const int M = 2000005; 19 20 struct edges { 21 int next, to, v; 22 edges() {} 23 edges(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {} 24 } e[M]; 25 26 int n, m, Tot, tot; 27 char mp[len][len]; 28 int w[len][len], first[N], dis[N]; 29 30 struct heap_node { 31 int v, to; 32 heap_node() {} 33 heap_node(int _v, int _to) : v(_v), to(_to) {} 34 }; 35 inline bool operator < (const heap_node &a, const heap_node &b) { 36 return a.v > b.v; 37 } 38 39 priority_queue <heap_node> h; 40 41 void Add_Edges(int x, int y, int z) { 42 e[++tot] = edges(first[x], y, z), first[x] = tot; 43 e[++tot] = edges(first[y], x, z), first[y] = tot; 44 } 45 46 inline void add_to_heap(const int p) { 47 for (int x = first[p]; x; x = e[x].next) 48 if (dis[e[x].to] == -1) 49 h.push(heap_node(e[x].v + dis[p], e[x].to)); 50 } 51 52 void Dijkstra(int S) { 53 memset(dis, -1, sizeof(dis)); 54 while (!h.empty()) h.pop(); 55 dis[S] = 0, add_to_heap(S); 56 int p; 57 while (!h.empty()) { 58 if (dis[h.top().to] != -1) { 59 h.pop(); 60 continue; 61 } 62 p = h.top().to; 63 dis[p] = h.top().v; 64 h.pop(); 65 add_to_heap(p); 66 } 67 } 68 69 void build_graph() { 70 int i, j; 71 for (i = 1; i <= n; ++i) 72 for (j = 1; j <= m; ++j) 73 if (mp[i][j] == '\') { 74 Add_Edges(w[i][j], w[i + 1][j + 1], 0); 75 Add_Edges(w[i + 1][j], w[i][j + 1], 1); 76 } else { 77 Add_Edges(w[i][j], w[i + 1][j + 1], 1); 78 Add_Edges(w[i + 1][j], w[i][j + 1], 0); 79 } 80 } 81 82 int main() { 83 int i, j; 84 scanf("%d%d", &n, &m); 85 for (i = 1; i <= n; ++i) 86 scanf("%s", mp[i] + 1); 87 for (i = 1; i <= n + 1; ++i) 88 for (j = 1; j <= m + 1; ++j) 89 w[i][j] = ++Tot; 90 build_graph(); 91 Dijkstra(1); 92 if (dis[Tot] != -1) printf("%d ", dis[Tot]); 93 else puts("NO SOLUTION"); 94 return 0; 95 }