博客

跳马问题

【问题描述】



在5*5格的棋盘上，有一只中国象棋的马，从（1,1）点出发，按日字跳马，它可以朝8个方向跳，但不允许跳出界或已跳过的格子上，要求跳遍每个棋盘。

回溯与搜索的思想

#include<bits/stdc++.h>
using namespace std;

int x[9]={0,-1,-2,-2,-1,1,2,2,1};//马的8种走向
int y[9]={0,2,1,-1,-2,-2,-1,1,2};
int xy[100][3];//记录走法
bool b[6][6];//标记是否走过了
int ans;//计数

void out()//打印
{
    ans++;
    cout<<ans<<endl;
    for(int i=1;i<=24;i++)
    {
        cout<<xy[i][1]<<xy[i][2]<<' ';
    }
    cout<<endl;
}

void dfs(int k)
{
    for(int i=1;i<=8;i++)
    {
        if((xy[k-1][1]+x[i]>=1)&&(xy[k-1][1]+x[i]<=5)&&(xy[k-1][2]+y[i]>0)&&(xy[k-1][2]+y[i]<6)&&(!b[xy[k-1][1]+x[i]][xy[k-1][2]+y[i]]))//不出界且没有走过
        {
            xy[k][1]=xy[k-1][1]+x[i];//记录结果
            xy[k][2]=xy[k-1][2]+y[i];
            b[xy[k][1]][xy[k][2]]=1;//标记
            if(k==24)
            {
                out();
            }
            else
            {
                dfs(k+1);
            }
            b[xy[k][1]][xy[k][2]]=0;//回溯
        }
    }
}

int main()
{
    xy[0][1]=1;//边界
    xy[0][2]=1;
    b[1][1]=1;
    dfs(1);
    return 0;
}