传送门 题意 给你一个N*N（2≤N≤100）的方格中，‘x’表示障碍，‘.’表示没有障碍（可以走），牛牛可以从一个格子走到他相邻的四个格子，但是不能走出这些格子。问牛牛从A点到B点最少需要转90度的弯几次。
思路 拐弯才要花费，把一个点拆成四个点，上下左右，从上到下 和 从左到右建双向边，边权为0；从上到左、从上到右、从下到左、从下到右建双向边，边权为1。建一个源点S和一个汇点T，S向A的四个方向的点建边，边权为0，B的四个方向的点向T建边，边权为1。最后跑dijkstra。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e2 + 7, INF = 0x3f3f3f3f; #define pr pair<int,int> typedef long long ll; char mp[maxn][maxn]; int n, sx, sy, ex, ey, S, T; int head[maxn*maxn*4], to[maxn*maxn*16], nex[maxn*maxn*16], edge[maxn*maxn*16], tot; void add(int x, int y, int z) { to[tot] = y; edge[tot] = z; nex[tot] = head[x]; head[x] = tot++; } bool final[maxn*maxn*4]; int d[maxn*maxn*4]; int dijkstra() { memset(final, 0, sizeof(final)); memset(d, INF, sizeof(d)); priority_queue<pr, vector<pr>, greater<pr> > que; que.push(make_pair(0, S)); d[S] = 0; while (!que.empty()) { int u = que.top().second; que.pop(); final[u] = true; for (int i = head[u]; ~i; i = nex[i]) { int v = to[i]; int len = edge[i]; if(!final[v] && d[v] > d[u] + len) { d[v] = d[u] + len; que.push(make_pair(d[v], v)); } } } return d[T]; } int main() { memset(head, -1, sizeof(head)); scanf("%d", &n); char s[10]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { scanf("%s", s), mp[i][j] = s[0]; if(mp[i][j] == 'A') sx = i, sy = j; if(mp[i][j] == 'B') ex = i, ey = j; } } //1 up ; 2 down ; 3 left ; 4 right for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { int up = 4 * n * (i - 1) + (j - 1) * 4 + 1, down = 4 * n * (i - 1) + (j - 1) * 4 + 2, left = 4 * n * (i - 1) + (j - 1) * 4 + 3, right = 4 * n * (i - 1) + (j - 1) * 4 + 4; add(up, down, 0); add(down, up, 0); add(left, right, 0); add(right, left, 0); add(up, left, 1); add(left, up, 1); add(up, right, 1); add(right, up, 1); add(down, left, 1); add(left, down, 1); add(down, right, 1); add(right, down, 1); if(i + 1 <= n && mp[i + 1][j] != 'x' && mp[i][j] != 'x') { int x = 4 * n * (i) + (j - 1) * 4 + 1; add(down, x, 0); add(x, down, 0); } if(j + 1 <= n && mp[i][j + 1] != 'x' && mp[i][j] != 'x') { int x = 4 * n * (i - 1) + (j) * 4 + 3; add(right, x, 0); add(x, right, 0); } } } S = n * n * 4 + 1, T = n * n * 4 + 2; int up = 4 * n * (sx - 1) + (sy - 1) * 4 + 1, down = 4 * n * (sx - 1) + (sy - 1) * 4 + 2, left = 4 * n * (sx - 1) + (sy - 1) * 4 + 3, right = 4 * n * (sx - 1) + (sy - 1) * 4 + 4; add(S, up, 0); add(S, down, 0); add(S, left, 0); add(S, right, 0); up = 4 * n * (ex - 1) + (ey - 1) * 4 + 1, down = 4 * n * (ex - 1) + (ey - 1) * 4 + 2, left = 4 * n * (ex - 1) + (ey - 1) * 4 + 3, right = 4 * n * (ex - 1) + (ey - 1) * 4 + 4; add(up, T, 0); add(down, T, 0); add(left, T, 0); add(right, T, 0); dijkstra(); if(d[T] == INF) printf("-1\n"); else printf("%d\n", d[T]); }