马踏棋盘算法

#include<iostream>
#include<stack>
using namespace std;
struct point{
	int x;
	int y;
};
stack<point *> sta;
int map[8][8];
int moved[8][2]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};
void dfs(int x,int y){
	int visited[8][8];
	memset(visited,0,sizeof(visited));
	//0表示没有访问过
	point *p=new point;
	p->x=x;
	p->y=y;
	point *temp;
	point *q;
	int count=0;
	sta.push(p);
	visited[x][y]=1;
	int a,b;
	count++;


  while(!sta.empty()){
	 q=sta.top();
	 if(count==16)
		 //64搜索不过来
		 break;
	 int flag=0;
	 for(int i=0;i<8;i++){
		 a=q->x+moved[i][0];
		 b=q->y+moved[i][1];
		 if(a>=0&&a<4&&b>0&&b<4&&(!visited[a][b])){
			 temp=new point;
			 temp->x=a;
			 temp->y=b;
			 visited[a][b]=1;
			 sta.push(temp);
			 count++;
          flag=1;//表示当前可以继续走下去，不需要回溯
		  //不是bfs,所以需要跳出
		  break;
	 }
  }
	 if(flag==0){
		 //不能再走下去了，要回溯
		 count--;
		 
		 //sta.pop();//这里好像会有内存泄漏
		 temp=sta.top();
		 a=temp->x;
		 b=temp->y;
		 visited[a][b]=0;
		 sta.pop();
		 delete temp;
    }
}
  int n=sta.size();
  cout<<n<<endl;
  for(int i=0;i<n;i++){
	 temp=sta.top();
	 a=temp->x;
	 b=temp->y;
	 cout<<a<<" "<<b<<"  ";
	 if(i%8==0)
		 cout<<endl;
	 sta.pop();
	 delete temp;
	 map[a][b]=(n-i);
  }
  /*for(int i=1;i<=64;i++){
	  cout<<map[i/8][i%8];
	  if(i%8==0)
		  cout<<endl;
  }
  */
}
int main(){
	int x,y;
	cin>>x>>y;
	dfs(x,y);
	return 0;
}

马踏棋盘算法,布布扣,bubuko.com

马踏棋盘算法

原文：http://blog.csdn.net/sn_zzy/article/details/22090453