1.txt

罗密欧与朱丽叶的算法

//   suanfa5_12.cpp   :   Defines   the   entry   point   for   the   console   application.   
  //   
  #include   <iostream>   
  using   namespace   std;   
    
  int   m;   
  int   n;   
  int   k;   
  static   int   dirs   =   0;   
  int   x;   
  int   y;   
  int   x1;   
  int   y1;   
  int   best   =   1000;   
  static   int   count   =   0;   
  int   dx[8]   =   {-1,   0,   1,   -1,   1,   -1,   0,   1};   
  int   dy[8]   =   {-1,   -1,   -1,   0,   0,   1,   1,   1};   
  static   int   **board;   
  static   int   **bestb;   
    
  void   search(int   dep,   int   x,   int   y,   int   di);   
  bool   stepok(int   x,   int   y);   
  void   save();   
    
  int   main(int   argc,   char*   argv[])   
  {   
  int   i;   
  int   j;   
  int   q;   
  int   p;   
    
  cin>>n>>m>>k;   
  board   =   new   int   *[m   +   1];   
  bestb   =   new   int   *[m   +   1];   
  for(i   =   0;   i   <=   m;   i++)   
  {   
  board[i]   =   new   int[n   +   1];   
  bestb[i]   =   new   int[n   +   1];   
  }   
  for(i   =   0;   i   <=   m;   i++   )   
  {   
  for(j   =   0;   j   <=   n;   j++)   
  {   
  board[i][j]   =   0;   
  bestb[i][j]   =   0;   
  }   
  }   
    
  for(i   =   1;   i   <=   k;   i++)   
  {   
  cin>>q>>p;   
  board[q][p]   =   -1;   
  }   
    
  cin>>x>>y;   
  cin>>x1>>y1;   
    
  search(1,   x,   y,   1);   
    
  cout<<dirs<<endl;   
  cout<<count<<endl;   
    
  for(i   =   1;   i   <=   m;   i++   )   
  {   
  for(j   =   1;   j   <=   n;   j++)   
  {   
  cout<<bestb[i][j]<<"   ";   
  }   
  cout<<endl;   
  }   
    
    
  return   0;   
  }   
    
  void   search(int   dep,   int   x,   int   y,   int   di)   
  {   
  if(dep   ==   m   *   n   -   k   &&   x   ==   x1   &&   y   ==   y1   &&   dirs   <=   best)   
  {   
  if(dirs   <   best)   
  {   
  best   =   dirs;   
  count   =   1;   
  save();   
  }   
  else   
  {   
  count++;   
  }   
  return;   
  }   
    
  if(dep   ==   m   *   n   -   k   ||   x   ==   x1   &&   y   ==   y1   ||   dirs   >   best)   
  {   
  return;   
  }   
  else   
  {   
  for(int   i   =   1;   i   <=   8;   i++)   
  {   
  if(stepok(x   +   dx[i],   y   +   dx[i]))   
  {   
  board[x   +   dx[i]][y   +   dx[i]]   =   dep   +   1;   
  if(di   !=   i)   
  {   
  dirs++;   
  }   
  search(dep   +   1,   x   +   dx[i],   y   +   dx[i],   i);   
  if(di   !=   i)   
  {   
  dirs--;   
  }   
  board[x   +   dx[i]][y   +   dx[i]]   =   0;   
  }   
  }   
  }   
  }   
    
  bool   stepok(int   x,   int   y)   
  {   
  return(x   >   0   &&   x   <=   n   &&   y   >   0   &&   y   <=   m   &&   board[x][y]   ==   0);   
  }   
    
  void   save()   
  {   
  for(int   i   =   1;   i   <=   n;   i++)   
  {   
  for(int   j   =   1;   j   <=m;   j++)   
  {   
  bestb[i][j]   =   board[i][j];   
  }   
  }   
  }