马的周游C语言实现

// Problem#: 1153  
// Submission#: 3079805  
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License  
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/  
// All Copyright reserved by Informatic Lab of Sun Yat-sen University  
//  
//  main.cpp  
//  马的周游  
//  
//  Created by liujan on 10/24/14.  
//  Copyright (c) 2014 liujan. All rights reserved.  
//  
  
#include <iostream>  
#include "vector"  
#include "memory.h"  
#include "algorithm"  
using namespace std;  
  
bool isvisited[8][8];  
int move_x[8] = { -2, -1, 1, 2, -2, -1, 1, 2 };  
int move_y[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };  
vector<int>route;  
  
struct Node{  
  int x, y;  
  int child;  
};  
  
bool cmp(Node a, Node b){  
  return a.child < b.child;  
}  
vector<Node> nextMove(Node current){  
  int y = current.y;  
  int x = current.x;  
  vector<Node>next;  
  for (int i = 0; i < 8; i++){  
    int tmpx = x + move_x[i];  
    int tmpy = y + move_y[i];  
    if (tmpx >= 0 && tmpx <= 7 && tmpy <= 7 && tmpy >= 0 && !isvisited[tmpy][tmpx]){  
      Node tmp;  
      tmp.x = tmpx;  
      tmp.y = tmpy;  
      tmp.child = 0;  
      next.push_back(tmp);  
    }  
  }  
  return next;  
}  
bool move(Node pos){  
  if (route.size() == 64){  
    for (size_t i = 0; i < route.size() - 1; i++){  
      cout << route[i] << " ";  
    }  
    cout << route[route.size() - 1] << endl;  
    return true;  
  }  
  else{  
    vector<Node> next = nextMove(pos);  
    for (int i = 0; i < next.size(); i++){  
      next[i].child = nextMove(next[i]).size();  
    }  
    sort(next.begin(), next.end(),cmp);  
  
    for (size_t i = 0; i < next.size(); i++){  
      int y = next[i].y;  
      int x = next[i].x;  
      isvisited[y][x] = true;  
      route.push_back(y * 8 + x + 1);  
      bool result = move(next[i]);  
      if (!result){  
        isvisited[y][x] = false;  
        route.pop_back();  
      }  
      else{  
        return true;  
      }  
    }  
    return false;  
  }  
}  
int main(){  
  int n;  
  while (cin >> n && n != -1)  
  {  
    for (int i = 0; i < 8; i++){  
      for (int j = 0; j < 8; j++)  
        isvisited[i][j] = false;  
    }  
    route.clear();  
    int y = (n - 1) / 8;  
    int x = n - y * 8 - 1;  
    Node head;  
    head.x = x;  
    head.y = y;  
    isvisited[y][x] = true;  
    route.push_back(n);  
    move(head);  
  }  
}             

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。