首页 » 技术分享 » 跳马问题

跳马问题

　
评论关闭　740次浏览

信息学奥赛一本通P248

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

输出前5个方案及总方案数。

代码:

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
int total,g[6][6];  //g[i][j]代表第几步跳到点（i，j）
bool p[6][6]; //记录点（i，j）是否走过
int dx[8]={1,2,2,1,-1,-2,-2,-1};
int dy[8]={-2,-1,1,2,2,1,-1,-2};
void print()
{
    total++;
    if(total>5) return;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=5;j++)
            cout<<setw(5)<<g[i][j];
        cout<<endl;
    }
    cout<<endl;
}
void dfs(int i,int j,int s)
{
    int k;
    for(k=0;k<8;k++)
    {
        if((i+dx[k])<=5&&(i+dx[k])>0&&(j+dy[k])<=5&&(j+dy[k]>0)) //未越界
        {
            if(!p[i+dx[k]][j+dy[k]]) //未走过
            {
                p[i+dx[k]][j+dy[k]]=true; //标记走过，
                g[i+dx[k]][j+dy[k]]=s; //记录第s步走在哪个点
                if(s==25) print(); //已经走了25步，输出
                else dfs(i+dx[k],j+dy[k],s+1); //寻找下一步落点
                p[i+dx[k]][j+dy[k]]=false; //回溯
            }
        }
    }
}
int main()
{
    total=0;
    memset(p,false,sizeof(p));
    g[1][1]=1; p[1][1]=true;
    dfs(1,1,2); //从(1,1)开始搜第2步怎么走
    cout<<"总方案数total:"<<total<<endl;
    return 0;
}

P302迷宫问题

代码：

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
int dx[8]={0,0,1,0,-1};
int dy[8]={0,1,0,-1,0};
bool f;
int n,m,i,j,desx,desy,soux,souy,head,tail,x,y,a[51],b[51],pre[51],map[51][51];
void print(int d)
{
    if(pre[d]!=0) print(pre[d]);
    cout<<a[d]<<","<<b[d]<<endl;
}
int main()
{
    int i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        cin>>map[i][j];
    cin>>soux>>souy;
    cin>>desx>>desy;
    head=0; tail=1;
    f=false;
    map[soux][souy]=-1;
    a[tail]=soux; b[tail]=souy; pre[tail]=0;
    while(head!=tail)
    {
        head++;
        for(i=1;i<=4;i++)
        {
            x=a[head]+dx[i]; y=b[head]+dy[i];
            if((x>0)&&(x<=n)&&(y>0)&&(y<=m)&&map[x][y]==0)
            {
                tail++;
                a[tail]=x; b[tail]=y; pre[tail]=head;
                map[x][y]=-1;
                if(x==desx&&y==desy)
                {
                    f=true;
                    print(tail);
                    break;
                }
            }
        }
        if(f) break;
    }
    if(!f) printf("no way.\n");
    return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：跳马问题，转载请注明来源！

赞 0