中国象棋中的跳马问题

一个小问题弄了半天！感觉下次出现这种问题需要冷静一下，不能一直闷头找，隔一段时间重新看会好一点！

题目描述

现在棋盘的大小不一定，由p，q给出，并且在棋盘中将出现障碍物（限制马的行动，与象棋走法相同）

输入

第一行输入n表示有n组测试数据。

每组测试数据第一行输入2个整数p,q，表示棋盘的大小(1<=p,q<=100)。
每组测试数据第二行输入4个整数，表示马的起点位置与终点位置。(位置的取值范围同p,q)
第三行输入m表示图中有多少障碍。
接着跟着m行，表示障碍的坐标。

输出

马从起点走到终点所需的最小步数。
如果马走不到终点，则输入“can not reach!”

样例输入

样例输出

1
can not reach!

提示

此题是一个搜索题，可用DFS或BFS，建议选择BFS(广搜)。一开始把马的起始点加入队列，然后用广搜的思想把此点能到达的其他点加入队列，这里需要一个数组用来记录此点在之前是否已经加入队列，如果加入过队列当中，就不需要再加入了，直到队列里的元素为空，或者搜索到了终点，搜索即停止，然后输出相应答案即可。

这道题并不难，就是HDU1372变一下，加了一个蹩脚的条件。前两天写的时候WA了十几回，想不通，感觉做法和标程差不多。今天拿来重新做，才发现了当时没有发现的一个重大问题。我在判断是否蹩脚的时候是从终点(v.x,v.y)判断的，但是应该是判断起跳点(u.x,u.y)能否到终点！！！一个小问题弄了半天！感觉下次出现这种问题需要冷静一下，不能一直闷头找，隔一段时间重新看会好一点。虽然用的stl的队列会慢很多，但幸好没有超时，就先这样吧，等复习A*的时候看能不能加速。

参考代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 struct pos
  8 {
  9     int x,y,ori;
 10 };
 11 pos dir[8]={{2,1,0},{2,-1,1},{-2,1,2},{-2,-1,3},{1,2,4},{-1,2,5},{1,-2,6},{-1,-2,7}};
 12 struct Node
 13 {
 14     int x,y,step;
 15 };
 16 queue<Node>que;
 17 int map[105][105];
 18 int vis[105][105];
 19 int p,q,sx,sy,ex,ey,ans;
 20 
 21 bool in(int a,int b)
 22 {
 23     if(a>0&&a<=p&&b>0&&b<=q&&!vis[a][b]&&map[a][b]==0) return true;
 24     return false;
 25 }
 26 
 27 bool can_move(int x,int y,int d)
 28 {
 29     if(d==0||d==1){
 30         if(map[x+1][y]==0) return true;
 31         return false;
 32     }
 33     if(d==2||d==3){
 34         if(map[x-1][y]==0) return true;
 35         return false;
 36     }
 37     if(d==4||d==5){
 38         if(map[x][y+1]==0) return true;
 39         return false;
 40     }
 41     if(d==6||d==7){
 42         if(map[x][y-1]==0) return true;
 43         return false;
 44     }
 45 }
 46 
 47 int bfs()
 48 {
 49     while(!que.empty()) que.pop();
 50     Node st;
 51     st.x=sx,st.y=sy,st.step=0;
 52     que.push(st);
 53     while(!que.empty())
 54     {
 55         Node u;
 56         u=que.front();que.pop();
 57 
 58         if(u.x==ex&&u.y==ey) return u.step;
 59 
 60         for (int i=0;i<8;i++)
 61         {
 62             Node v=u;
 63             v.x=u.x+dir[i].x,v.y=u.y+dir[i].y;
 64             if(in(v.x,v.y))
 65             {
 66                 if(can_move(u.x,u.y,dir[i].ori))//是u.x,u.y并不是v.x,v.y!!!
 67                 {
 68                     v.step=u.step+1;
 69                     vis[v.x][v.y]=1;
 70                     que.push(v);
 71                 }
 72             }
 73         }
 74     }
 75     return -1;
 76 }
 77 
 78 int main()
 79 {
 80 
 81     freopen("F:\4.txt", "r", stdin);
 82     freopen("F:\2.txt", "w", stdout);
 83     int n,m;
 84     scanf("%d",&n);
 85     while(n--)
 86     {
 87         scanf("%d%d",&p,&q);
 88         scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
 89         scanf("%d",&m);
 90         memset(vis,0,sizeof(vis));
 91         vis[sx][sy]=1;
 92         memset(map,0,sizeof(map));
 93         while(m--)
 94         {
 95             int a,b;
 96             scanf("%d%d",&a,&b);
 97             map[a][b]=1;
 98         }
 99         ans=-1;
100         ans=bfs();
101         if(ans>-1) printf("%d
",ans);
102         else printf("can not reach!
");
103     }
104     return 0;
105 }

View Code 1

正好大概了解了一下怎样造数据：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int main()
{
    int n, p, q, sx, sy, ex, ey, m;
    int i, zhangx, zhangy;
    freopen("F:\4.txt", "w", stdout);
    srand(time(NULL));
    n = 1000;
    printf("%d
", n);
    while (n--)
    {
        p = rand() % 100 + 1;
        q = rand() % 100 + 1;
        printf("%d %d
", p, q);
        sx = rand() % p + 1;
        sy = rand() % q + 1;
        ex = rand() % p + 1;
        ey = rand() % q + 1;
        printf("%d %d %d %d
", sx, sy, ex, ey);
        m = rand() % p;
        printf("%d
", m);
        for (i = 1; i <= m; i++) {
            zhangx = rand() % p + 1;
            zhangy = rand()&q + 1;
            printf("%d %d
", zhangx, zhangy);
        }
    }
    return 0;
}

View Code 2