Implementing Graph Algorithms

Okay just saw my previous code had

        if(grid[x][y]==1)
            continue;

but I've removed that

// if(top.x <= 0 || top.x>n) continue;
       // if (top.y <= 0 || top.y >m) continue;

I tried using the print statements and it appears that these two statements are causing the trouble as it skips the rest of the statements. If i skip those two however, it results into an infinte loop but it does go through rest of the statements.

updated code:

    #include <iostream>
    #include <stdio.h>
    #include <algorithm>
    #include <stack>
    #include <queue>
    #include <vector>
    using namespace std;
        int result=0;
bool visited[210][210];
int grid[210][210];
int dist[210][210];
int n, m;
class node
{
public:
int x;
int y;
node() : x( 0 ), y( 0 ) {}
node( int pX, int pY ) : x( pX ), y( pY ) {}

/*node(int pX, int pY)
    {
        x=pX;
        y=pY;
    }*/
};


    queue<node> s;
void TraverseGrid()
{

    while(s.empty()!=true)
{
    node top=s.front();
    cout<<"top.x "<<top.x<<" top.y: "<<top.y<<" visited: "<<visited[top.x][top.y]<<endl;
    s.pop();
    cout<<"FLAG 1 PASSED"<<endl;
   if(top.x <= 0 || top.x>n) continue;
    cout<<"FLAG 2 PASSED"<<endl;
    if (top.y <= 0 || top.y >m) continue;
    cout<<"FLAG 3 PASSED"<<endl;
    cout<<visited[top.x][top.y]<<endl;
    cout<<"FLAG 4 PASSED"<<endl;
    visited[top.x][top.y]=true;
    if(visited[top.x][top.y]==true)cout<<"YES VISITED"<<endl;
    cout<<visited[top.x][top.y]<<endl;
    if(!visited[top.x+1][top.y])
    {


        dist[top.x+1][top.y]=1+dist[top.x][top.y];

            s.push(node(top.x+1, top.y));
    }

    if(!visited[top.x][top.y+1])
    {dist[top.x][top.y+1]=1+dist[top.x][top.y];
    s.push(node(top.x, top.y+1)); }

    if(!visited[top.x][top.y-1])
    {dist[top.x][top.y-1]=1+dist[top.x][top.y];s.push(node(top.x, top.y-1)); }

    if(!visited[top.x-1][top.y])
    { dist[top.x-1][top.y]=1+dist[top.x][top.y];s.push(node(top.x-1, top.y));}

}

}
int main()
{
    int t;
    cin>>t;
    while(t--)
{
    int n, m;
    cin>>n>>m;

for(int i=1; i <= 200; i++)
    for(int j=1; j <= 200; j++)
        {dist[i][j]=9999; visited[i][j]=false;}

for(int i=1; i <= n; i++)
    for(int j=1; j <= m; j++)
        {
            int temp;
            cin>>temp;
            grid[i][j]=temp;
            if(temp==1)
                s.push(node(i, j));
            dist[i][j]=0;
        }
        TraverseGrid();


for(int i=1; i <= n; i++){
    for(int j=1; j <= m; j++)
       cout<<dist[i][j];
       cout<<endl;
}

}



}

Should I try to implement it again from scratch?

Hi Leppy.
Well please guide me on how to actually calculate the distance to nearest white pixel. I get it that all white pixels are to be pushed into the queue. Sure, but before that I'd like to know how to calculate distance to nearest pixel. Below is my slightly modified BFS:

#include <queue>
#include <stack>
#include <algorithm>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef struct node {
    int x;
    int y;
};
bool fills[400][400];
int dist[400][400];
int graph[400][400];
void bfs (node start)
{
    queue <node> s;
    s.push(start);
    fills[start.x][start.y]=true;
    while (s.empty() == false)
    {
        int top = s.front();
        s.pop();
        //now generate all the transitions to the nodes.
          for (int i = -1; i <= 1; i++) {
          for (int j = -1; j <= 1; j++) {
                //
          //int tempdist = abs(start.x-(start.x-i))+abs(start.y-(start.y+i));
          if(graph[start.x+i][start.y+j]==0)
            dist[start.x][start.y]+=1;
          }
          }
    }
}

Thanks a lot leppy. Finally I now have a clear idea and intuition behind the BFS Algorithm. So after lots of trial and error and trying this and trying that -
I managed to get "AC" on this problem. However it took 0.63 seconds! I'll try to use scanf/printf next time, but please let me know whether it is possible to improve runtime here:

#include <queue>
#include <stack>
#include <algorithm>
#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
int tempdistance=0;
class node {
    public:
    int x;
    int y;
    int d;
    node( int pX, int pY, int D ) : x( pX ), y( pY ), d(D) {}
};
int n; int a,b;
bool fills[400][400];
int dist[400][400];
int finaldist[400][400];
int graph[400][400];
int dx[] = { -1, 1, 0, 0};
int dy[] = {0, 0, -1, 1}; int r,c;
  queue <node> s;
void bfs ()
{
    while (s.empty() == false)
{
    node top = s.front();
    s.pop();
    //now generate all the transitions to the nodes.
      for (int i = 0; i < 4; i++) {
    {
            //
      //int tempdist = abs(start.x-(start.x-i))+abs(start.y-(start.y+i));

         r = top.x + dx[i];
         c = top.y + dy[i];
        //cout<<"r: "<<r<<"  c: "<<c<<endl;
       // cout<<fills[r][c]<<endl;

        if(r >= 0 && r < a &&  c >=0 && c < b && fills[r][c]==false)
        {
            fills[r][c]=true;// cout<<fills[r][c]<<endl;
            dist[r][c]=top.d+1; //cout<<dist[r][c]<<endl;
            if(dist[r][c] < finaldist[r][c])
                finaldist[r][c]=dist[r][c];
            s.push(node(r,c,top.d+1));
        }
      }
      }


}
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>a;
        cin>>b; int rows=1;cin.ignore();
    for(int i=0; i < a; i++)
    {
        int c=0;
        string input;
        getline(cin, input);
        while(c<b)
        {
            fills[i][c]=false;
        graph[i][c]=0;
        dist[i][c]=0;
        finaldist[i][c]=9999;
            int tempnumber=input[c]-'0';
            //cout<<tempnumber<<endl;
            if(tempnumber==1)
            {
                s.push(node(i,c, 0));
             finaldist[i][c]=0;
            }
    c++;
    }



}





bfs();
for(int i=0; i < a; i++)
    {
        for(int j=0; j < b; j++)
        {

         cout<<finaldist[i][j]<<" ";
        }
        cout<<endl; }

}
}