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];
queue<vertex> que;

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

void bfs(int n, int m, int sval, int& ans){
    while(!que.empty())     que.pop();
    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(){
    int n, m;
    while(~scanf("%d%d", &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++){
                scanf("%d", &arr[i][j]);
                sval = min(arr[i][j], sval);
            }
        }
        bfs(n, m, sval, ans);
        printf("%d\n", ans);
    }
    return 0;
}

/*
Main.cc:13:7: error: 'vertex' was not declared in this scope
 queue<vertex> que;
       ^
Main.cc:13:13: error: template argument 1 is invalid
 queue<vertex> que;
             ^
Main.cc:13:13: error: template argument 2 is invalid
Main.cc:13:18: error: invalid type in declaration before ';' token
 queue<vertex> que;
                  ^
Main.cc: In function 'void bfs(int, int, int, int&)':
Main.cc:22:16: error: request for member 'empty' in 'que', which is of non-class type 'int'
     while(!que.empty())     que.pop();
                ^
Main.cc:22:33: error: request for member 'pop' in 'que', which is of non-class type 'int'
     while(!que.empty())     que.pop();
                                 ^
Main.cc:31:21: error: request for member 'push' in 'que', which is of non-class type 'int'
                 que.push(u);
                     ^
Main.cc:35:16: error: request for member 'empty' in 'que', which is of non-class type 'int'
     while(!que.empty()){
                ^
Main.cc:36:24: error: request for member 'front' in 'que', which is of non-class type 'int'
         vertex u = que.front();
                        ^
Main.cc:37:13: error: request for member 'pop' in 'que', which is of non-class type 'int'
         que.pop();
             ^
Main.cc:48:53: error: request for member 'push' in 'que', which is of non-class type 'int'
             if(max_steps[v.x][v.y] < v.steps)   que.push(v);
                                                     ^
*/

Double click to view unformatted code.


Back to problem 17