Implementing Graph Algorithms

[theconqueror_sof]

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?

[leppyr64]

Not those.

[leppyr64]

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

[theconqueror_sof]

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

}



}

[theconqueror_sof]

Should I try to implement it again from scratch?

[leppyr64]

If you learn well that way, yes.

[theconqueror_sof]

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

[leppyr64]

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.

[theconqueror_sof]

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

}
}

[leppyr64]

Scanf and printf will save a lot of time. Good job!