题目描述

坦克车只能水平或垂直方向上移动到相邻的区，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转。

样例

输入样例：
5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

输出样例：
10

思路：迷宫(注意一些问题，每次走的是正负能量辐射区，写一个数组记录正负能量辐射分别为1和-1， 目标位置都为0，然后走的时候判断取相反数)

C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

char a[N][N];
int d[N][N], g[N][N];
int n, s, e;

int bfs()
{
    queue<PII> q;

    int x1 = s / n, y1 = s % n;
    int x2 = e / n, y2 = e % n;

    //cout << x1 << y1 << " " << x2 << y2 << endl;

    memset (d, -1, sizeof d);
    q.push({x1, y1});

    d[x1][y1] = 0;

    int dx[5] = {-1, 1, 0, 0}, dy[5] = {0, 0, 1, -1};

    while (q.size())
    {
        PII t = q.front();
        q.pop();

        if (t.first == x2 && t.second == y2)
        {
            return d[x2][y2];
        }

        for (int i = 0;i < 4;i ++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < n && d[x][y] == -1 && 
            (g[t.first][t.second] == -g[x][y] || g[t.first][t.second] == 0
             || g[x][y] == 0))
            {
                //cout << x << "---->" << y << endl;
                d[x][y] = d[t.first][t.second] + 1;
                q.push ({x, y});
            }
        }
    }

    return -1;
}

int main()
{
    cin >> n;
    for (int i = 0;i < n;i ++)
    {
        for (int j = 0;j < n;j ++)
        {
            cin >> a[i][j];
            if (a[i][j] == 'A') s = i * n + j;
            if (a[i][j] == 'B') e = i * n + j;
        }
    }
    for (int i = 0;i < n;i ++)
    {
        for (int j = 0;j < n;j ++)
        {
            if (a[i][j] == '+') g[i][j] = 1;
            if (a[i][j] == '-') g[i][j] = -1;
        }
    }

    cout << bfs() << endl;

    return 0;
}