加载中…
个人资料
N紫O色I
N紫O色I
  • 博客等级:
  • 博客积分:0
  • 博客访问:14,152
  • 关注人气:3
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
正文 字体大小:

马的遍历,跳马

(2018-10-16 15:47:11)
分类: 搜索回溯
一)例55:马的遍历
中国象棋半张棋盘如图4(a)所示。马自左下角往右上角跳。今规定只许往右跳,不许往左跳。比如图4(a)中所示为一种跳行路线,并将所经路线打印出来。打印格式为:0,0->2,1->3,3->1,4->3,5->2,7->4,8…
马的遍历,跳马

【算法分析】
       如图4(b),马最多有四个方向,若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为:
1:  (i,j)→(i+2,j+1);  (i<3,j<8)
2:  (i,j)→(i+1,j+2);  (i<4,j<7)
3:  (i,j)→(i-1,j+2);  (i>0,j<7)
4:  (i,j)→(i-2,j+1);  (i>1,j<8)
     搜索策略:
        S1:A[1]:=(0,0);
        S2:从A[1]出发,按移动规则依次选定某个方向,如果达到的是(4,8)则转向S3,否则继续搜索下一个到达的顶点;
        S3:打印路径。
算法分析:
凡是这种題目,都是用dx[],dy[]数组,按棋子走动的要求,定义好上下左右的对应走法;然后用于更新,每一步搜索时的“下一步”位置。马还有一个特点,就是abs(x-dx)+abs(y-dy)的值==3,然后就可以按照走小兵的办法,完成马遍历。有时侯,会限制“马跳动的方向”,那就是dx/dy组合方向的次序问題,调整即可。
输入:
8 4
输出:…………共37行;
using namespace std;
int a[100][2],t=0;
int x[4]    ={2,1,-1,-2},    y[4]    ={1,2,2,1};
int search(int);
int print(int);
int m,n;
int main(){
    cin>>m>>n;
    a[1][0]    =0;    a[1][1]    =0;
    search(2);
    }
int search(int i)
{
    for(int j=0;j<=3;j++)
        if(    a[i-1][0] +x[j] >=0 &&     a[i-1][0] +x[j]    <=n
            &&     a[i-1][1]    +y[j]    >=0 &&     a[i-1][1]    +y[j]    <=m    )
            {
                a[i][0]    =a[i-1][0]    +x[j];
                a[i][1]    =a[i-1][1]    +y[j];
                if(a[i][0]==n && a[i][1]==m) print(i);
                else search(i+1);
            }
   
    }
int print(int ii){
        t++;
        cout<<t<<": ";
        for(int i=1;i<=ii-1;i++)
            cout<<a[i][0]<<","<<a[i][1]<<"-->";
        cout<<n<<";"<<m<<endl;
    }

二)例5.8 跳马问題
跳马问题。在5*5格的棋盘上,有一只中国象棋的马,从(1,1)点出发,按日字跳马,它可以朝8个方向跳,但不允许出界或跳到已跳过的格子上,要求在跳遍整个棋盘。
输出前5个方案及总方案数。
输出格式示例:
   16   21   10   25
20   11   24   15    22
17      19      9
12        23   14
   18    13      5
算法分析:
除了上題一样的方向数组,界定马的跳跃方向以外,这里只需要明白,dfs(k)中的k相当于步数,找个地方存起这个步数,也就可以继续往下面跳。dfs还可以把其他参数传下去,比如这步的x,y坐标等。
这种題目,一般也可以采用块搜索完成。
using namespace std;

    int u[8]    ={1,2,2,1,-1,-2,-2,-1};
    int v[8]    ={-2,-1,1,2,2,1,-1,-2};
    int a[100][100]={0},num=0;
    int dfs(int,int,int);   
    int print();
int n;

int main(){
    cin>>n;
    a[1][1]    =1;
    dfs(1,1,2);
    cout<<num<<endl;
     
   
    int dfs(int i,int j,int k){
        if(k>n*n)
            print();
        else   
        for(int l=0;l<=7;l++)
        {
            int x    =i+u[l];int y    =j+v[l];
            if(x<=n && x>=1 && y<=n && y>=1 && (! a[x][y]))
            {
                a[x][y]    =k;
                dfs(x,y,k+1);
                a[x][y]    =0;
                }
            }
        }
       
        int print()
        {
            num++;
            if(num<=n){
                for(int l=1;l<=n;l++)
                {
                    for(int kk=1;kk<=n;kk++)
                        cout<<setw(5)<<a[l][kk];
                    cout<<endl;   
                    }
                cout<<endl;
                }
            }

三)openjudge马走日
 马在中国象棋以日字形规则移动。
    请编写一段程序,给定n*m大小的棋盘,以及马的初始位置(x,y),要求不能重复经过棋盘上的同一个点,计算马可以有多少途径遍历棋盘上的所有点。
输入
    第一行为整数T(T < 10),表示测试数据组数。
    每一组测试数据包含一行,为四个整数,分别为棋盘的大小以及初始位置坐标n,m,x,y。(0<=x<=n-1,0<=y<=m-1, m < 10, n < 10)
输出
    每组测试数据包含一行,为一个整数,表示马能遍历棋盘的途径总数,0为无法遍历一次。
样例输入
    1
    5 4 0 0
样例输出
    32
using namespace std;
int a[101][101];
int xx[10]={1,1,-1,-1,2,-2,2,-2};
int yy[10]={2,-2,2,-2,1,1,-1,-1};
int cnt    =0,num=0;
int n,m;
void dfs(int x,int y)
{
    for(int i=0;i<8;i++){
        int xi    =x+xx[i];
        int yi    =y+yy[i];
        if(xi>=0 && xi < n && yi>=0 && yi < m && a[xi][yi]==0)
        {
            a[xi][yi]=1;
            num++;
            if(num==n*m) cnt++;
            else  dfs(xi,yi);
            a[xi][yi]=0;           
            num--;
            }
        }
    }

int main(){
    int nn;
    cin>>nn;
    for(int i=1;i<=nn;i++){
        int x,y;
        cnt=0;
        cin>>n>>m>>x>>y;
        memset(a,0,sizeof(a));
        a[x][y]    =1,num    =1;
        dfs(x,y);   
        cout<<cnt<<endl;
        }
    }

四)p1443马的遍历;
有一个n*m的棋盘(1<=400),在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入格式:一行四个数据,棋盘的大小和马的坐标
输出格式:一个n*m的矩阵,代表马到达某个点最少要走几步(左对齐,宽5格,不能到达则输出-1)
输入样例#1:
3 3 1 1
输出样例#1:
      
   -1    
      
1)深搜解法
using namespace std;
#define NUM 401
int a[NUM][NUM];
int xx[10]={0,1,1,-1,-1,2,-2,2,-2};
int yy[10]={0,2,-2,2,-2,1,1,-1,-1};
int cnt    =0;
int n,m;
void dfs(int x,int y,int k)
{
    if(k>200) return;
    a[x][y]=k;
    for(int i=1;i<=8;i++)
    {
        int xi    =x+xx[i];
        int yi    =y+yy[i];
        if(xi>=1 && xi<=n && yi>=1 && yi<=m && (a[xi][yi]==-1 || a[xi][yi]>k+1))
                dfs(xi,yi,k+1);
        }
    }
int main(){
        int x,y;
        cnt=0;
        cin>>n>>m>>x>>y;
        memset(a,-1,sizeof(a));
        dfs(x,y,0);   
        //cout<<cnt<<endl;
        for(int i=1;i<=n;i++)
             
            for(int j=1;j<=m;j++)       
                printf("%-5d",a[i][j]);
            cout<<endl;
        }
    }

2)宽搜解法
#include "queue"
using namespace std;
#define NUM 401
struct node{int x;int y;};
queue < node > q;
int a[NUM][NUM];
int dx[10]={0,1,1,-1,-1,2,-2,2,-2};
int dy[10]={0,2,-2,2,-2,1,1,-1,-1};
int cnt    =0;
int n,m;
void bfs(int x,int y)
{
    node h;
    h.x=x,h.y=y;
    q.push(h);a[x][y]=0;
    do{
    for(int i=1;i<=9;i++)
    {
          =q.front();
        int xx=h.x+dx[i],   yy=h.y+dy[i];
        if(a[xx][yy]==-1 && xx>=1 && xx<=n && yy>=1 &yy<=m)
        {
            node tl;
            tl.x=xx,           tl.y=yy ;
            a[xx][yy]=a[h.x][h.y]+1;
            q.push(tl);
            }
        }
        q.pop();   
        }while(! q.empty());
     

int main(){
        int x,y;
        cnt=0;
        cin>>n>>m>>x>>y;
        memset(a,-1,sizeof(a));
        bfs(x,y);   
        //cout<<cnt<<endl;
        for(int i=1;i<=n;i++)
             
            for(int j=1;j<=m;j++)       
                printf("%-5d",a[i][j]);
            cout<<endl;
        }
    }
   


0

阅读 收藏 转载 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

新浪公司 版权所有