CSU 1224 ACM小组的古怪象棋

E - ACM小组的古怪象棋 Time Limit:1000MS    Memory Limit:131072KB    64bit IO Format:%lld & %llu SubmitStatusPracticeCSU 1224

Description

ACM小组的Samsara和Staginner对中国象棋特别感兴趣，尤其对马（可能是因为这个棋子的走法比较多吧）的使用进行深入研究。今天他们又在 构思一个古怪的棋局:假如Samsara只有一个马了，而Staginner又只剩下一个将，两个棋子都在棋盘的一边，马不能出这一半棋盘的范围，另外这 一半棋盘的大小很奇特(n行m列)。Samsara想知道他的马最少需要跳几次才能吃掉Staginner的将(我们假定其不会移动)。当然这个光荣的任 务就落在了会编程的你的身上了。

Input

每组数据一行，分别为六个用空格分隔开的正整数n,m,x1,y1,x2,y2分别代表棋盘的大小n,m,以及将的坐标和马的坐标。（1<=x1,x2<=n<=20,1<=y1,y2<=m<=20,将和马的坐标不相同）

Output

输出对应也有若干行，请输出最少的移动步数,如果不能吃掉将则输出“-1”(不包括引号)。

Sample Input

8 8 5 1 4 5

Sample Output

3

Hint

---

BFS.

多了一步判断马是否“蹩腿”。

#include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #define N 25 using namespace std; typedef struct {int x,y, step; }node; int dx[8]={1,-1,-2,-2,-1,1,2,2}; int dy[8]={2,2,1,-1,-2,-2,-1,1}; int vis[N][N]; int n,m,kstartx,kstarty,kendx,kendy; queue <node> q; int bfs(int x,int y) {int i,j,xx,yy;while(!q.empty())q.pop();node fir;fir.step=0;fir.x=x;fir.y=y;memset(vis,0,sizeof(vis));vis[x][y]=1;q.push(fir);while(!q.empty()){node fro=q.front();q.pop();i=fro.x;j=fro.y;if(i==kendx&&j==kendy){return fro.step;}node nxt;for(int k=0;k<8;k++){xx=i+dx[k],yy=j+dy[k];if(xx<0 || yy<0 || xx>=n || yy>=m || vis[xx][yy]) continue;if(dx[k]==2&&kendy==j&&kendx==(i+1)) continue;if(dx[k]==-2&&kendy==j&&kendx==(i-1)) continue;if(dy[k]==2&&kendx==i&&kendy==(j+1)) continue;if(dy[k]==-2&&kendx==i&&kendy==(j-1)) continue;if(xx==kendx&&yy==kendy) return fro.step+1;vis[xx][yy]=1;nxt.step=fro.step+1;nxt.x=xx;nxt.y=yy;q.push(nxt);}}return -1; } int main() {while(scanf("%d%d%d%d%d%d",&n,&m,&kendx,&kendy,&kstartx,&kstarty)>0){kstartx--,kstarty--,kendx--,kendy--;printf("%d\n",bfs(kstartx,kstarty));}return 0; }

总结

以上是生活随笔为你收集整理的CSU 1224 ACM小组的古怪象棋的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。