[USACO07FEB] Bronze Lilypad Pond B

题目描述

为了让奶牛们娱乐和锻炼，农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了 M 行 N 列个方格（1 ≤ M, N ≤ 30） 。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。

贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。

贝西的舞步很像象棋中的马步：每次总是先横向移动 M1 (1 ≤ M1 ≤ 30)格，再纵向移动 M2 (1 ≤ M2 ≤ 30, M1≠M2)格，或先纵向移动 M1 格，再横向移动 M2 格。最多时，贝西会有八个移动方向可供选择。

给定池塘的布局和贝西的跳跃长度，请计算贝西从起点出发，到达目的地的最小步数，我们保证输入数据中的目的地一定是可达的。

输入格式

第一行：四个用空格分开的整数：M，N，M1 和 M2

第二行到 M + 1 行：第 i + 1 行有 N 个用空格分开的整数，描述了池塘第

i 行的状态：0 为水，1 为莲花，2 为岩石，3 为贝西所在的起点，4 为贝西想去

的终点。

输出格式

第一行：从起点到终点的最少步数。

样例 #1

样例输入 #1

4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0

样例输出 #1

2

方向向量可变的bfs问题

#include<bits/stdc++.h>
using namespace std;

typedef pair<int , int> PII;
const int N = 40;
int m,n,m1,m2;      //m行n列
char g[N][N];
int dist[N][N];

//数组模拟队列
PII q[N * N];
int hh = 0;
int tt = -1;
int bfs(int x , int y , int dx[] , int dy[])
{
    q[++tt] = {x , y};
    memset(dist,-1,sizeof dist);
    dist[x][y] = 0;
    while(hh <= tt)
    {
        auto t = q[hh++];
        for(int i = 0; i < 8; i++)
        {
            int a = t.first + dx[i];
            int b = t.second + dy[i];

            if(a < 1 || b < 1 || a > m || b > n) continue;
            if(g[a][b] == '0' || g[a][b] == '2') continue;
            if(dist[a][b] == 0 || dist[a][b] != -1) continue;

            q[++tt] = {a,b};
            dist[a][b] = dist[t.first][t.second] + 1;
            if(g[a][b] == '4') return dist[a][b];
        }
    }
}

int main()
{
    cin>>m>>n>>m1>>m2;
    int dx[] = {-m1,-m2,-m2,-m1,m1,m2,m2,m1};
    int dy[] = {m2,m1,-m1,-m2,-m2,-m1,m1,m2};
    //0为水，1为莲花，2为岩石，3为贝西所在的起点，4为贝西想去
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            cin>>g[i][j];

    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            if(g[i][j] == '3')
            {
                cout<<bfs(i,j,dx,dy)<<endl;
                break;
            }

    return 0;
}