SPOJ - BITMAP

BITMAP.cpp

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

template <class T> int size(const T &x) {return x.size();}
template <class T> T mod(T a, T b) { return (b + (a % b)) % b;}

#define F first
#define S second
#define PB push_back
#define endl '\n'
#define rep(i, a, b) for(__typeof(a) i=a; i<(b); i++)
#define iter(it, c) for(__typeof((c).begin()) it=(c).begin(); \
 it != (c).end(); it++)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;

const int INF = ~(1 << 31);
const double EPS = 1e-9;
const double PI = acos(-1);

int M[183][183], S[183][183];

int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void bfs(int n, int m, queue<ii> &q) {

    while(!q.empty()) {
        ii front = q.front(); q.pop();

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

            int x = front.F + dir[i][0];
            int y = front.S + dir[i][1];

            if(x >= n || y >= m) continue;
            if((S[front.F][front.S] + 1) >= S[x][y])
                continue;

            S[x][y] = S[front.F][front.S] + 1;
            q.push(ii(x, y));
        }

    }


}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string line;
    int t, n, m;

    cin >> t;
    while(t--) {
        cin >> n >> m;

        queue<ii> q;
        for(int i=0; i<n; i++) {
            if(i < n) cin >> line;
            for(int j=0; j<m; j++) {
                S[i][j] = INF; M[i][j] = -1;

                if(i < n && j < m)
                    M[i][j] = line[j] - '0';

                // Save all the white pixels
                if(M[i][j] == 1) {
                    q.push(ii(i, j));
                    S[i][j] = 0;
                }

            }
        }
        bfs(n, m, q);
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(j) cout << ' ';
                cout << S[i][j];
            } cout << endl;
        }
    }

    return 0;
}