• Source 
    1. // Author: Ashis Kumar Chanda
    2. // CSE, DU
    3.  
    4. /** Find shortest path in 2d Matrix cell
    5.  
    6.     In graph problem we get node & adj node. Using node we make a adj Matrix
    7.     But In this problem, each cell is node & adj cell is adj node
    8.     So, to find adj node we need to compute r-1, c-1 ....
    9.  
    10.     There also some obstacle at cell, identified them as 9999999 value
    11.     initially all cell value -1
    12.     source cell value 0
    13.  
    14.     At first guess about normal BFS code, then look at it
    15.     We no need to Relaxation
    16.  
    17.      */
    18.  
    19. #include<stdio.h>
    20. #include<vector>
    21. #include<queue>
    22.  
    23. #include<string.h>
    24. #include<stdlib.h>
    25.  
    26. #define inf 9999
    27. #define SIZE 1009
    28. #define loop(a,init,n) for(a=init;a<n;a++)
    29.  
    30. using namespace std;
    31.  
    32. int r,c;
    33. int mat[SIZE][SIZE];
    34. //int color[100];
    35. //int D[100];
    36.  
    37. //void BFS(int source);
    38. void BFS(int sourceX, int sourceY );
    39. bool valid(int x, int y)
    40. {
    41.     if( (x>=0 && x<r) && (y>=0 && y<c) )
    42.         return true;
    43.     else
    44.         return false;
    45. }
    46.  
    47. void init()
    48. {
    49.     memset( mat, -1, sizeof(int)*SIZE*SIZE);
    50. }
    51. int main()
    52. {
    53.     int x,y,j,i,n, obstacle;
    54. 	while(scanf("%d%d",&r,&c) !=EOF && r!=0 && c!=0){
    55. 	scanf("%d",&obstacle);
    56.     init();
    57.  
    58. 	for(i=0;i<obstacle;++i)
    59. 	{
    60. 		scanf("%d%d",&x,&n);
    61. 		for(j=0; j<n; j++){
    62.             scanf("%d",&y);
    63.             mat[x][y]= inf;
    64. 		}
    65. 	}
    66.  
    67. //	puts("Give source :");
    68. 	scanf("%d%d",&x,&y );
    69.  
    70. 	BFS(x,y);
    71.     scanf("%d%d",&x,&y );       // destination
    72.  
    73. /*
    74.     loop(i,0,r){
    75.         loop(j,0,c)
    76.             printf("%4d ",mat[i][j]);
    77.         printf("\n");
    78.     }
    79.   */
    80.     printf("%d\n", mat[x][y]-1);
    81. 	}
    82.  
    83. return 0;
    84. }
    85.  
    86.  
    87. void BFS(int sourceX, int sourceY )
    88. {
    89.     int x,y;
    90.  
    91. 	mat[sourceX][sourceY]=1;
    92.  
    93. 	//color[source]=1;
    94. 	queue<int>Q;
    95. 	Q.push(sourceX);
    96. 	Q.push(sourceY);
    97.  
    98. 	while(!Q.empty())
    99. 	{
    100. 		x = Q.front();
    101. 		Q.pop();
    102. 		y = Q.front();
    103. 		Q.pop();
    104.  
    105. 		int ucost = mat[x][y];
    106.                                             // initially all -1, so mat[x][y]<1 means new node
    107.                 if( valid(x-1, y) && mat[x-1][y]<1 ){
    108.                     Q.push(x-1);
    109.                     Q.push(y);
    110.                     mat[x-1][y]= ucost+1;
    111.                  }
    112.                 if(  valid(x+1, y) && mat[x+1][y]<1  ){
    113.                     Q.push(x+1);
    114.                     Q.push(y);
    115.                     mat[x+1][y]=  ucost+1;
    116.                  }
    117.                 if(  valid(x, y-1) && mat[x][y-1]<1 ){
    118.                     Q.push(x);
    119.                     Q.push(y-1);
    120.                     mat[x][y-1]=  ucost+1;
    121.                  }
    122.                 if(  valid(x, y+1) && mat[x][y+1]<1 ){
    123.                     Q.push(x);
    124.                     Q.push(y+1);
    125.                     mat[x][y+1]=  ucost+1;
    126.                 }
    127. 	}
    128. }