Converting a 2D matrix into a graph

Question

I am facing a problem while converting a given 2D matrix containing both invalid and valid points into a graph with only valid nodes. The problem goes like this. I have a 2D matrix like

# # # # #
# . C C #
# S # # #
# . . E #
# # # # # 

I want to find the shortest distance from S to E keeping in mind that I have to cover all 'C' and '#' acts as a wall and '.' acts as free path. Now I want to convert this matrix into a graph containing only the valid nodes. Kindly help me out.

n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
 for k=1 to n:
   for i=1 to n:
    for j=1 to n:
        d[i][j] = min(d[i][j], d[i][k] + d[k][j])

shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
  shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

Answer 1

A 2d matrix of the characters is a perfectly fine graph representation for this problem.

Each matrix element (i,j) is a node. Assuming you can only step East, West, North, South, there exist 0 to 4 undirected edges from this node to its neighbors (i +or- 1, j +or- 1) as determined by simply testing the character in each location.

You could also test for i,j values that are out of range (negative or too big), but if there is always a "wall" around the border as you have shown, this is not needed. The wall serves as a sentinel.

Building a general purpose structure to represent a graph embedded in a grid is a waste of time and memory.