SPOJ/HackerRank BITMAP

//Unsorted Ideas: 

২ডি পিক্সেল গ্রিড। ০ মানে ব্ল্যাক আর ১ মানে হোয়াইট পিক্সলে ।
প্রত্যেকটা ০ পিক্সেল থেকে তার সবচে নিকটবর্তী ১ পিক্সেল এর ডিসটেন্স লাগবে । 

ডিসটেন্স বের করার ফরমুলা দেয়া আছে।    ->    d( p₁, p₂)=| i₁-i₂|+| j₁-j₂|. 

নাইভ অ্যাপ্রোচ প্রত্যেকটা জিরো কে সোর্স বানিয়ে বার বার  বিএফেস করে দেখতে হবে তার সবচে কাছাকাছি কোথায় ১ আছে। অনেকগুলা জিরোর জন্য টাইম লিমিট খাবে ।

যেহেতু এখানে ডিসট্যান্স সিমেট্রিক তাই আমরা উলটা করলেই পারি। সবগুলা ১ থেকে বিএফেস চালায়ে যতক্ষন ছোট ডিস্টেন্স দিয়ে জিরোর ডিস্টেন্স কে আপডেট করা যায় ততক্ষন করব। 

আগে থেকেই ছোট থাকলে কিছু করার দরকার নাই, কিন্তু আগের ১ থেকে করেস্পন্ডিং ০ র দূরত্ব কারেন্টটার চাইতে বড় হলে লেটেস্ট ১ থেকে ছোট ডিসটেন্স দিয়ে ওই জিরো কে আপডেট করে দিব আমরা । 

ডায়াক্সট্রা তে যেভাবে আপডেট করি আমরা নোড করে মিনিমাম কস্ট দিয়ে সেরকম অনেকটা। যাই হোক... এইত্তো আর কিছু না... অকা! 

Code:

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 123456789
#define sz 202

string sa[sz];
ll r,c;

struct point
{
    int x,y;
};

bool vis[sz][sz];
int d[sz][sz];

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

void init()
{
    REP(i,sz) REP(j,sz) vis[i][j] = 0, d[i][j] = INT_MAX;
}

void BFS(int i, int j)
{
    mem(vis,0);

    point s;
    s.x = i, s.y = j;

    queue<point> Q;
    Q.push(s);

    vis[s.x][s.y] = 1;
    d[s.x][s.y] = 0;

    point u,v;

    while(!Q.empty())
    {
        u = Q.front();
        Q.pop();


        REP(i,4)
        {
            v.x = u.x + dx[i];
            v.y = u.y + dy[i];

            if(v.x>=0 and v.x<r and v.y>=0 and v.y<c)
            {
                 // boundary satisfies then,  enter if we have unvisited 0

                if( vis[v.x][v.y]==0 and sa[v.x][v.y]=='0' )
                {
                    vis[v.x][v.y] = 1;

                    //update 0 only if it can be relaxed to lower cost than the previous distance

                    if(d[v.x][v.y] > d[u.x][u.y] + 1)
                    {
                        d[v.x][v.y] = d[u.x][u.y] + 1;
                        Q.push(v);
                    }
                }
            }
        }
    }
}

int main()
{
    ll t,cs=0;

    scl(t);
    while(t--)
    {
        scll(r,c);
        REP(i,r) cin>>sa[i];

        int cnt = 0;

        init();

        REP(i,r)
        {
            REP(j,c)
            {
                if(sa[i][j]=='1') BFS(i,j);
            }
        }

        REP(i,r)
        {
            REP(j,c)
            {
                if(j) putchar(' ');
                printf("%d", d[i][j]);
            }
            puts("");
        }
    }
        return 0;
}