题目描述

bfs做法

样例

#include <iostream>
#include <cstdio>
#include <algorithm>
#include<queue>
using namespace std;

int w, m, n,step = 0;
int a[10005][10005];
int main()
{
    cin >> w >> m >> n;

    int index = 1;
    pair<int,int> p,p1;
    queue<pair<int,int>> q;
    for(int i = 0; index <= max(m, n); i ++)
    {
        if(i % 2 == 0)
            for(int j = 0; j < w; j ++)
            {

                a[i][j] = index ++;
                if(a[i][j] == m)
                p = {i,j};
                if(a[i][j] == n)
                p1 = {i,j};

            }

        else
            for(int j = w - 1; j > -1; j --)
            {

                a[i][j] = index ++;
                if(a[i][j] == n)
                p1 = {i,j};
                if(a[i][j] == m)
                p = {i,j};
            }

    }
    q.push(p);
    a[p.first][p.second] = 0;
    int dx [4] = {0,1,0,-1},dy[4] = {1,0,-1,0};
    while(!q.empty())
    {
        int size = q.size();
        step ++;
        for(int i = 0;i < size;i++)
        {
            pair<int,int> temp = q.front();
            q.pop();
            if(temp.first == p1.first && temp.second == p1.second)
            {
            cout << step - 1;
            return 0;
            }
            for(int j = 0;j < 4;j++)
            {
                int x = temp.first + dx[j];
                int y = temp.second + dy[j];
                if(x >= 0 && x < max(m, n) && y >= 0 && y < w && a[x][y])
                {
                    a[x][y] = 0;
                    q.push({x,y});
                }
            }

        }

    }
    return 0;
}