两遍bfs ~

#include <cstdio>

#include <cstdlib>

//#include <cmath>

#include <map>

#include <set>

#include <stack>

#include <vector>

#include <sstream>

#include <string>

#include <cstring>

#include <algorithm>

#include <iostream>

#define maxn 1010

#define INF 0x7fffffff

#define inf 10000000

#define ull unsigned long long

#define ll long long

using namespace std;

int g[maxn][maxn], m, n, vis[maxn][maxn], dis1[maxn][maxn], dis2[maxn][maxn], x1, x2, y1, y2;

int q[maxn*maxn];

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

void bfs1(int x, int y)

{

    int front = 0, rear = 0, u;

    vis[x][y] = 1;

    u = x*m+y;

    dis1[x][y] = 0;

    q[rear++] = u;

    while(front < rear)

    {

        u = q[front++];

        x = u/m, y = u%m;

        for(int i = 0; i < 4; ++ i)

        {

            int nx = x+dx[i], ny = y+dy[i];

            if(nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] != 1 && !vis[nx][ny])

            {

                int v = nx*m+ny;

                q[rear++] = v;

                vis[nx][ny] = 1;

                dis1[nx][ny] = dis1[x][y]+1;

            }

        }

    }

//    puts("");

//    for(int i = 0; i < n; ++ i)

//    {

//        for(int j = 0 ; j < m; ++ j)

//        {

//            printf("%d ", dis1[i][j]);

//        }

//        puts("");

//    }

}

void bfs2(int x, int y)

{

    int front = 0, rear = 0, u;

    vis[x][y] = 1;

    u = x*m+y;

    dis2[x][y] = 0;

    q[rear++] = u;

    while(front < rear)

    {

        u = q[front++];

        x = u/m, y = u%m;

        for(int i = 0; i < 4; ++ i)

        {

            int nx = x+dx[i], ny = y+dy[i];

            if(nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] != 1 && !vis[nx][ny])

            {

                int v = nx*m+ny;

                q[rear++] = v;

                vis[nx][ny] = 1;

                dis2[nx][ny] = dis2[x][y]+1;

            }

        }

    }

//    puts("");

//    for(int i = 0; i < n; ++ i)

//    {

//        for(int j = 0 ; j < m; ++ j)

//        {

//            printf("%d ", dis2[i][j]);

//        }

//        puts("");

//    }

}

void init()

{

    for(int i = 0; i < n; ++ i)

        for(int j = 0 ; j < m; ++ j)

        {

            dis1[i][j] = dis2[i][j] = inf;

        }

}

int main()

{

    while(scanf("%d%d", &m, &n) == 2)

    {

        init();

        for(int i = 0; i < n; ++ i)

            for(int j = 0 ; j < m; ++ j)

            {

                scanf("%d", &g[i][j]);

                if(g[i][j] == 2)

                    x1 = i, y1 = j;

                else if(g[i][j] == 3)

                    x2 = i, y2 = j;

            }

        memset(vis, 0, sizeof(vis));

        bfs1(x2, y2);

        memset(vis, 0, sizeof(vis));

        vis[x2][y2] = 1;

        bfs2(x1, y1);

        int ans = inf;

        for(int i = 0; i < n; ++ i)

            for(int j = 0 ; j < m; ++ j)

            {

                if(g[i][j] == 4)

                    ans = min(ans, dis1[i][j]+dis2[i][j]);

            }

        printf("%d\n", ans);

    }

    return 0;

}