cpp2.cpp

王晓东 算法第五章课后习题 罗密欧与朱丽叶的回溯算法

#include <iostream.h>
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 i;
 int j;
 int q;
 int p;
 
 cin>>n>>m>>k;
 board = new int *[n + 1];
 bestb = new int *[n + 1];
 for(i = 0; i <= m; i++)
 {
  board[i] = new int[m + 1];
  bestb[i] = new int[m + 1];
 }
 for(i = 0; i <= n; i++ )
 {
  for(j = 0; j <= m; 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);
 for(i = 1; i <= n; i++ )
 {
  for(j = 1; j <= m; j++)
  {
   cout<<bestb[i][j]<<" ";
  }
  cout<<endl;
 }
cin>>i;
 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 + dy[i]))
   {
    board[x + dx[i]][y + dy[i]] = dep + 1;
    if(di != i)
    {
     dirs++;
    }
    search(dep + 1, x + dx[i], y + dy[i], i);
    if(di != i)
    {
     dirs--;
    }
    board[x + dx[i]][y + dy[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];
  }
 }
}