 # Grid representation as a graph

I am thinking of a grid and suppose in the grid ‘#’ represents that the way is blocked and ‘.’(dot without quotes) represents there is a way.So if A is inside the grid then he can walk inside when he found way(.)
e.g.,

``````#######
#### A####
##.#.##
##.#.##
##...##
#######
``````

for the above example, A found the way and he reaches to other place like this below in picture:

``````#######
##.####
##.#A##
##.#.##
##...##
#######
``````

If I am thinking this problem as a graph then How I will represent this grid as a graph ?
How to represent this as an adjacency list ?
I am new to graph just stuided BFS only, please answer in easy words

Suppose I have to find the maximum distance between two dots(.), here there is no source and destination, how to do that ?

``````#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######``````

can u provide the problem link…i.e. the ques that u r trying!!!

@kunal361 I am not trying any question, but I studied somewhere that if any question is in the form of grid, then that question will be considered as graph problem, so I randomly select this case and thought how to form graph with this grid, what I realized is every co-ordinate can be considered as node and top,bottom,left and right as its edge, but I don’t know how to represent it using adjacency list or matrix so basically I want to know how to code for this grid.

can u relate ur ques to this problem statement…http://www.codechef.com/problems/BYTESD …??

hmmm yes, this can be considered as the same problem…

then…for such a problem there is no need to create the adj list…u just need to start at a particular location and then traverse through the array in all 2,3 or 4 possible directions till u get to the destination…for this you can use the floodfill algorithm!!!

algo:-

``````floodfill(int i,int j)
{
visited[i][j]=1;   //mark the position as visited
if(array[i][j]==destination)
print reached
if(!visited[i+1][j]&&(array[i+1][j]=='.'||array[i+1][j]==destination))
floodfill(i+1,j)
if(!visited[i-1][j]&&(array[i-1][j]=='.'||array[i-1][j]==destination))
floodfill(i-1,j)
if(!visited[i][j+1]&&(array[i][j+1]=='.'||array[i][j+1]==destination))
floodfill(i,j+1)
if(!visited[i][j-1]&&(array[i][j-1]=='.'||array[i][j-1]==destination))
floodfill(i-1,j)
}
``````

for getting a good idea of this algo u can view my solution to the above problem on the problem page and ask nething that u may fail to understand… @thanks for the reply, I will study this algorithm and 1 more thing,If suppose, there is no source and destination, you just have to find the maximum path you can traverse only inside the grid, then this algorithm will also work there ? for e.g., I include one more example in my problem statement

//