騎士游歷（二）

問題描述：設有一個n×n的棋盤（n≤10），在棋盤上的任意一點A(x,y)有一中國象棋<馬>,<馬>走的規(guī)則同前，但取消<馬>只能向右走的條件。試找出一條路徑，使<馬>不重復地走遍棋盤上的每一個點。其中左下角的坐標為(1,1)右上解的從標為(n,n)。

輸入：

6

3 4

輸出：(輸出其中任意一種并輸出到文件)

36 13 10 23 4 15

11 22 5 14 9 24

20 35 12 1 16 3

29 32 21 6 25 8

34 19 30 27 2 17

31 28 33 18 7 26

解題方法：用深搜模擬跳馬，用a數(shù)組來存儲方案，當馬已經(jīng)跳了n*n步時，輸出當前方案

#include<iostream> #include<cstdio> using namespace std; int n,p,n1,n2,a[12][12]; const int dx[8]={2,1,-1,-2,-2,-1,1,2};//馬可以走的方向（行） const int dy[8]={1,2,2,1,-1,-2,-2,-1};//馬可以走的方向（列） void js(int x,int y,int z) {if (z>n*n)//判斷是否填滿{p=1;//記錄for (int i=1;i<=n;i++)//循環(huán)行{for (int j=1;j<=n;j++)//循環(huán)列printf("%d ",a[i][j]);//輸出printf("\n");//換行}return;}if (p==1) return;//如果輸出過了，就退出for (int i=0;i<8;i++)if (x+dx[i]>0&&x+dx[i]<=n&&y+dy[i]>0&&y+dy[i]<=n)//判斷是否出界if (a[x+dx[i]][y+dy[i]]==0)//是否跳過{a[x+dx[i]][y+dy[i]]=z;//記錄js(x+dx[i],y+dy[i],z+1);//望一個方向跳a[x+dx[i]][y+dy[i]]=0;//回溯} }int main() {scanf("%d",&n);scanf("%d %d",&n1,&n2);memset(a,0,sizeof(a));p=0;a[n1][n2]=1;js(n1,n2,2); }

總結

以上是生活随笔為你收集整理的【深搜】骑士游历（二）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。