测试了一下，发现五篇题解输出都不一样。哈哈。

本来想着拿 SPFA 的那篇题解做 std 出一份数据，想想还是不放心自己写了份 Dij，发现过不去。查了半天原来是 SPFA 题解在拓展完一个节点之后忘记把队列标记值改成 $\verb!false!$ 了，假了。

所以最后拿我的 Dij 出的数据。只有 @vеctorwyx 的题解能过。检查了一下代码，确实是对的（把边权为 $2$ 的边视作两条边权为 $1$ 的边，这样就可以 bfs 了）。

其他题解已打回。

附 Dij 代码：

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;

const int MAXN = 1200 + 3;
const int D[3][4][2] = {
    {{1, 0}, {0, 1}, {-1, 0}, {0, -1}},
    {{2, 0}, {0, 2}, {-2, 0}, {0, -2}},
    {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
};

char H[MAXN][MAXN];
int  F[MAXN][MAXN];

using state = pair<int, pair<int, int> >;

int main(){
    // freopen("2.in", "r", stdin);

    int n;
    cin >> n;
    for(int i = 1;i <= n;++ i){
        for(int j = 1;j <= n;++ j)
            cin >> H[i][j];
    }
    
    priority_queue<state, vector<state>, greater<state> > Q;
    if(H[1][1] != '*')
        Q.push(make_pair(1, make_pair(1, 1)));
    if(H[1][n] != '*')
        Q.push(make_pair(1, make_pair(1, n)));
    if(H[n][1] != '*')
        Q.push(make_pair(1, make_pair(n, 1)));
    
    while(!Q.empty()){
        auto [d, u] = Q.top();
        auto [x, y] = u;
        Q.pop();

        if(F[x][y]){
            continue;
        }
        F[x][y] = d;
        if(x == n && y == n){
            cout << d << endl;
            return 0;
        }

        int type = H[x][y] - 'A';
        for(int i = 0;i < 4;++ i){
            int nx = x + D[type][i][0];
            int ny = y + D[type][i][1];
            int nd = d + (H[x][y] == 'C' ? 2 : 1);

            if(1 <= nx && nx <= n && 1 <= ny && ny <= n && H[nx][ny] != '*' && !F[nx][ny]){
                Q.push(make_pair(nd, make_pair(nx, ny)));
            }
        }
    }
    cout << "No answer" << endl;
    return 0;
}