View Code of Problem 17

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 505;
const int inf = 0x3f3f3f3f;

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
int arr[N][N];
int max_steps[N][N];

struct vertex{
    int x;
    int y;
    int steps;
};

void bfs(int n, int m, int sval, int& ans){
    queue<vertex> que;
    memset(max_steps[0], -1, sizeof(max_steps));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(arr[i][j] == sval){
                vertex u;
                u.x = i;
                u.y = j;
                u.steps = 0;
                que.push(u);
            }
        }
    }
    while(!que.empty()){
        vertex u = que.front();
        que.pop();
        //if(max_steps[u.x][u.y] >= u.steps)  continue;
        //max_steps[u.x][u.y] = u.steps;
        ans = max(ans, u.steps);

        for(int i = 0; i < 4; i++){
            vertex v;
            v.x = u.x + dx[i];
            v.y = u.y + dy[i];
            v.steps = u.steps + 1;
            if(arr[v.x][v.y] < arr[u.x][u.y])   continue;
            //if(max_steps[v.x][v.y] < v.steps)
            que.push(v);
        }
    }
}

int main(){
    //ios::sync_with_stdio(false);
    int n, m;
    while(cin >> n >> m){
        int ans = 0;
        memset(arr[0], -1, sizeof(arr));
        int sval = inf;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin >> arr[i][j];
                sval = min(arr[i][j], sval);
            }
        }
        bfs(n, m, sval, ans);
        cout << ans << endl;
    }
    return 0;
}