//  SIMPLE CONNECTION CHECKING PROGRAM for MAZEs or IMAGES
//    program tested using g++ version 2.7.2
#include <String.h>
#include <fstream.h>
#include <stdio.h>
#define MAXROW 200   // max size of image is 200 x 200
#define MAXCOL 200
//  Global image and object data used by all procedures
  String imagetitle;
  int numberofrows,  numberofcolumns,  connectivity;
  char image[MAXROW][MAXCOL];   

void input_image () 
{
  fstream Infile;
  String filename;
  int row, col;
  char newlinechar;
  cout << "Please give name of file containing the input image: " << endl;
  cin >> filename;
  Infile.open ( filename, ios::in );
  Infile >> imagetitle;   
  cout << "Image title is : " << imagetitle << endl;
  Infile >> numberofrows;  Infile >> numberofcolumns;
  cout << "and the image size is " << numberofrows 
           << " x " << numberofcolumns << endl;
  for(row=0; row<numberofrows; row++)  
    { for(col=0;col<numberofcolumns;col++)  
         Infile.get(image[row][col]); // i/o method does not skip blanks
      Infile.get(newlinechar); // consume end of line char
    }
  Infile.close();
} 
void output_image ()
{
    int row,col;
    cout << endl;  
    cout << "Your image is as follows: " << endl;
    for(row=0; row<numberofrows; row++)  
      { for(col=0; col<numberofcolumns; col++)
          cout << image[row][col]; 
        cout << endl;
      }
    cout << endl;
}
void propagate_color(int r, int c, char color)

/* r and c MUST be within the image array bounds AND image MUST
   have a border of all 'X's. This function calls itself back to
   color the neighbors of neighbors, etc. until background is reached
   or a pixel of this same color is reached (to prevent infinite looping).
   Connectivity should be either 4 or 8; not 4 is taken to be 8 */

{  if (image[r][c] != ' ') return; // if background or already colored 
   image[r][c] = color;  // color the center pixel itself 
   // now color all of the neighbors recursively 
   // propagate through the 4-neighbors
   propagate_color(r-1,c,color);    propagate_color(r,c-1,color);    
   propagate_color(r,c+1,color);    propagate_color(r+1,c,color);
   if ( connectivity == 4 ) return; // connectivity is global variable 
   // propagate through the 8-neighbors as well
   propagate_color(r-1,c-1,color);    propagate_color(r-1,c+1,color);
   propagate_color(r+1,c-1,color);    propagate_color(r+1,c+1,color);
 }
main () 
{
  int start_r, start_c, goal_r, goal_c;

  cout << endl << "=====MAZE RUNNER === CONNECTIVITY CHECKER=====" << endl;
  input_image ();
  output_image();
  cout << "Please give start_r, start_col, goal_r, goal_c and" << endl;
  cout << "the program will decide if there is an open connecting path."
       << endl;
  cin >> start_r >> start_c >> goal_r >> goal_c;
  cout << " What connectivity? ( 4 or 8 ) - " << endl;  cin >> connectivity;
  if ( (image[start_r][start_c] != ' ') | (image[goal_r][goal_c] != ' ') )
     cout << "No connecting blank path since endpoints not both blank" << endl;
  else { // pour ink from start and see if it colors goal
         propagate_color(start_r, start_c, '+');
         if ( image[goal_r][goal_c] != '+' )
             cout << "No connecting blank path found." << endl;
         else cout << "Connecting path found." << endl; 
       }
  output_image();
}