26 / 30
Aug 2014

Thanks leppy, but I'm still confused. Here is what I have done so far:

  1. By default initialized distance to some random number, and initialized the "visited[i][j]" to false.
  2. Accepted input for grid from the user (well, the problem clearly does not have a whitespace between pixels, so string parsing will be required, but lets worry about that later).
    3.Whichever grid pixels were "1", I pushed them into queue s.

  3. Now how can I modify my BFS for distance?
    [code]
    int main()
    {
    int t;
    cin>>t;
    while(t--)
    {
    int n, m;

for(int i=1; i <= n; i++)
    for(int j=1; j <= m; j++)
       {
           distance[i][j]=99999; 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(1,1);



}[/code]

BFS
[code]
int TraverseGrid(int x, int y)
{

    while(s.empty()==false)
{
    node top=s.front();
    s.pop();
  if(grid[x][y]==1)
        continue;
    if(top.x < 0 || top.x>=n) continue;
    if (top.y < 0 || top.y >=m) continue;[/code]

You know the distance at (x,y). So the distance at (x+1,y), if it hasn't already been reached, will be the distance at (x,y)+1.

I could get only this far:

    #include <iostream>
    #include <stdio.h>
    #include <algorithm>
    #include <stack>
    #include <queue>
    #include <vector>
    using namespace std;
        int result=0;
bool visited[600][400];
int grid[200][200];
int dist[200][200];
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(int x, int y)
{

    while(s.empty()==false)
{
    node top=s.front();
    s.pop();
    if(grid[x][y]==1)
        continue;
    if(top.x < 0 || top.x>=n) continue;
    if (top.y < 0 || top.y >=m) continue;
    if(visited[top.x][top.y]) continue;
    visited[top.x][top.y]=true;


    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 <= n; i++)
    for(int j=1; j <= m; 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(1,1);


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

}



}

Why? Put some debugging print statements in there. See what your code is doing. This is how you fix things in the real world and is a valuable lesson to learn.

Yeah it is not performing the BFS, i.e. while debugging I figured out that it just pops the elements which I had pushed, and even though

!visited[][]

evaluates correctly, it does not go inside the "if" blocks!

You fix that by removing the statement that's preventing it from getting there.

I'm really trying to help you, but I really don't want to just write your code for you. You need to think and learn. The reason that your code is failing right now is painfully obvious if you were to take the time to walk through it with the test case and see what it is doing.

Is it because of "continue" statements?

        if(top.x < 0 || top.x>n) continue; //removed top.x >=n
        if (top.y < 0 || top.y >m) continue;
        if(visited[top.x][top.y]) continue;
        visited[top.x][top.y]=true;

I'm accessing array 1 through m/n (not 0 based indexing) so I guess the last index n or m is valid, so I have now removed "=" sign from the first two "if" blocks. I also tried removing if(visited[]) continue, but still the same! Is there something else I am missing?

Not those. Stop guessing and actually debug your code. Put print statements after every line so you can see what it is doing.

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;
}

}



}

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;
          }
          }
    }
}

The key to a breadth first search is that it crawls outward from the start. Take a cup of water and pour it on the floor. See how the water radiates outward? Now take two glasses and pour them at the same time from two different points. See how the water spreads outward but stops when it reaches water?

When you are pushing a new cell onto the queue is when you should be updating the distance and visited status, not when it comes off the queue. The distance to a white cell for the newly reached node is one more than the distance to a white cell for the node being reached from. Your code that you have written below is doing that and would work for a single white cell.

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; }

}
}

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 35 27d

Want to read more? Browse other topics in C and C++ or view latest topics.