Copyright (C), 2008
File name: 软件设计提高题（17.cpp）
Author: 计06-1 高战
Description:
Others: ....
Function List: // 主要函数列表，每条记录应包括函数名及功能简要说明
void TrackBoard::init(int i,int j) //初始化棋盘还开始位置
void TrackBoard::solve(int i, int j, int k, bool& ok) //看问题能否解决
void TrackBoard::onePath(int i,int j,int &g,int &h,int dir) //下一步的方向选择
void TrackBoard::print() //打印出棋盘
History:
<author> <time> <version > <desc>
*****************************************************/
#include <iostream>
#include <vector>
using namespace std;
class TrackBoard
{
public:
TrackBoard(int n,int i,int j);
void onePath(int i,int j,int &g,int &h,int dir);
bool hasPath(int i,int j,int &g,int &h,int dir);
void solve(int i, int j, int k, bool& ok);
void print();
void printBool();
void init(int i,int j);
private:
int nRows;
vector<vector<int> > board;
enum trackDir{WN1,WN2,NE1,NE2,ES1,ES2,SW1,SW2};
};
TrackBoard::TrackBoard(int n,int i,int j)
{
nRows=n;
init(i,j);
}
void TrackBoard::init(int i,int j) //初始化棋盘还开始位置
{
vector<int> vint(nRows,0);
board=vector<vector<int> >(nRows,vint);
board[i][j]=1;
}
void TrackBoard::solve(int i, int j, int k, bool& ok) //看问题能否解决
{
if(k>nRows*nRows)
{
ok=true;
}
else
{
for(int dir=WN1; dir<=SW2; dir++)
{
int g,h;
if (hasPath(i,j,g,h,dir)==true)
{
board[g][h]=k;
solve(g,h,k+1,ok);
if(ok==true)
{
return; //使用此句得到一个解
}
else
{
board[g][h]=0;
}
}
}
ok=false;
}
}
void TrackBoard::onePath(int i,int j,int &g,int &h,int dir) //下一步的方向选择
{
if(dir==WN1) {
g=i-1;h=j-2;
}
else if(dir==WN2) {
g=i-2;h=j-1;
}
else if(dir==NE1) {
g=i-2;h=j+1;
}
else if(dir==NE2) {
g=i-1;h=j+2;
}
else if(dir==ES1) {
g=i+1;h=j+2;
}
else if(dir==ES2) {
g=i+2;h=j+1;
}
else if(dir==SW1) {
g=i+2;h=j-1;
}
else{
g=i+1;h=j-2;
}
}
bool TrackBoard::hasPath(int i,int j,int &g,int &h,int dir) // 下一步的方向控制
{
onePath(i,j,g,h,dir);
原文请找腾讯752018766优,文-论'文.网http://www.youerw.com/ void TrackBoard::print() //打印出棋盘
{
for(int i=0;i<nRows;i++)
{
for(int j=0;j<nRows;j++)
cout<<board[i][j]<<" ";
cout<<endl;
}
}
int main()
{
int n=5,i,j;
bool ok=false;
cout<<"********************5*5的骑士巡游问题*****************************"<<endl;
cout<<"输入开始位置（i,j）"<<endl;
cin>>i>>j;
TrackBoard tb(n,i-1,j-1);
tb.solve(i-1,j-1,2,ok);
if (ok==true) {
cout<<"OK!"<<endl;
tb.print();
}
else
cout<<"NO!"<<endl;
return 0;}