fork download
copy 
  1. #include<iostream>
  2. #include<queue>
  3. #include<cstdio>
  4. #include<cstring>
  5. #define max 1005
  6. using namespace std;
  7.  
  8. int grid[max][max]={0},r,c;
  9. int si,sj,ei,ej;
  10. queue<int> qi,qj;
  11. void push_q(int i,int j) {
  12.   qi.push(i);
  13.   qj.push(j);   
  14. }
  15.  
  16. void pop_q() {
  17.   qi.pop();
  18.   qj.pop();     
  19. }
  20.  
  21. void adj(int u,int v) {
  22.   if( grid[u][v-1] == 0 && v>0) {
  23.     push_q(u,v-1);
  24.     grid[u][v-1] = grid[u][v]+1;    
  25.   }
  26.   if( grid[u][v+1] == 0 && v<c) {
  27.     push_q(u,v+1);
  28.     grid[u][v+1] =grid[u][v]+1;    
  29.   }
  30.     if( grid[u-1][v] == 0 && u>0) {
  31.     push_q(u-1,v);
  32.     grid[u-1][v] =grid[u][v]+1;    
  33.   }
  34.   if( grid[u+1][v] == 0 && u<r) {
  35.     push_q(u+1,v);
  36.     grid[u+1][v] =grid[u][v]+1;    
  37.   }
  38. }
  39.  
  40. void print_q(queue<int> q){
  41.      int s;
  42.      while(!q.empty()){
  43.            s=q.front();
  44.            cout<<s<<",   ";
  45.            q.pop();            
  46.      }
  47.      cout<<endl;
  48. }
  49.  
  50. void findpath(int si,int sj,int ei,int ej){
  51.   int u,v;
  52.   grid[si][sj] = 0;
  53.   push_q(si,sj);
  54.   while(!qi.empty() && !qj.empty()){
  55.       u=qi.front();
  56.       v=qj.front();
  57.       if(ei==u && ej==v) break;
  58.       pop_q();
  59.       adj(u,v);
  60.   }
  61. }
  62.  
  63. void reset() {   
  64.      int i,j;
  65.      while(!qi.empty() && !qj.empty()){
  66.        qi.pop();
  67.        qj.pop();
  68.      }
  69.      for(i=0;i<r;i++)
  70.       for(j=0;j<c;j++)
  71.         grid[i][j]=0;
  72. }
  73.  
  74. int main(){
  75.  int i,j,t,row,col,n;
  76.  while(1) {
  77.    scanf("%d%d",&r,&c);
  78.    if(r==0 && c==0) break;
  79.    scanf("%d",&t);
  80.    for(i=0;i<t;i++) {
  81.      scanf("%d %d",&row,&n);
  82.      for(j=0;j<n;j++){
  83.        scanf("%d",&col);
  84.        grid[row][col] = 1;
  85.      } 
  86.    }
  87.    scanf("%d%d",&si,&sj);
  88.    scanf("%d%d",&ei,&ej);
  89.    findpath(si,sj,ei,ej);
  90.    printf("%d\n",grid[ei][ej]);
  91.    reset();
  92.  }
  93.  return 0;   
  94. }
  95.  
Success #stdin #stdout 0s 7388KB
comments (?)
stdin
copy 
3 5
3
0 1 1
1 2 1 3
2 1 3
0 0
2 5
0 0
stdout
copy 
9
https://ideone.com/wgicOE
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!