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

用bfs做比較容易，類似于走迷宮求最短路，但是這個題wa了一次，是因為沒有考慮蹩馬腳的問題，還有沒有注意到不能到達輸出-1的問題。vis[ ][ ]是存放著從馬一開始的位置到馬能走到的位置的步數，最后函數輸出將的位置值。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <cmath>
struct node//記錄位置的結構體
{
? ? int x;
? ? int y;
};
node jpos;
node mpos;
using namespace std;
queue<node> qu;
int n,m;
int vis[22][22];
int dx[8]={1, 1, -1,-1, 2, 2,-2,-2};
int dy[8]={2, -2, -2,2,1,-1,1,-1};
int bfs(node dpos,node sta,int m,int h)
{
? ? int cnt=0,nx,ny;
? ? qu.push(sta);
? ? node p,n;
? ? while(!qu.empty())
? ? {
? ? ? ? //cout<<"ok";
? ? ? ? n=qu.front();
? ? ? ? cnt=++vis[n.x][n.y];
? ? ? ? qu.pop();
? ? ? ? for(int i=0;i<8;i++)
? ? ? ? {
? ? ? ? ? ? nx=n.x+dx[i];
? ? ? ? ? ? ny=n.y+dy[i];
? ? ? ? ? ? if(nx>=0 && nx<h && ny>=0&&ny<m && vis[nx][ny]==-1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(n.y-ny==-2&&n.x==dpos.x) continue;
? ? ? ? ? ? ? ? if(n.y-ny== 2&&n.x==dpos.x) continue;
? ? ? ? ? ? ? ? if(n.y-ny==-1&&n.y==dpos.y) continue;
? ? ? ? ? ? ? ? if(n.y-ny== 1&&n.y==dpos.y) continue;
? ? ? ? ? ? ? ? p.x=nx;
? ? ? ? ? ? ? ? p.y=ny;
? ? ? ? ? ? ? ? vis[p.x][p.y]=cnt;
? ? ? ? ? ? ? ? //cout<<vis[p.x][p.y]<<" "<<p.x<<" "<<p.y<<endl;
? ? ? ? ? ? ? ? qu.push(p);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return vis[dpos.x][dpos.y]--;
}


int main()
{
? ? int x1,y1,x2,y2;
? ? while(scanf("%d %d %d %d %d %d",&n,&m,&x1,&y1,&x2,&y2)!=EOF)
? ? {
? ? ? ? memset(vis,-1,sizeof(vis));
? ? ? ? jpos.x=x1-1;jpos.y=y1-1;
? ? ? ? mpos.x=x2-1;mpos.y=y2-1;
? ? ? ? vis[mpos.x][mpos.y]=0;
? ? ? ? bfs(jpos,mpos,m,n);
? ? ? ? if(vis[jpos.x][jpos.y]==-2) printf("-1\n");
? ? ? ? else printf("%d\n",vis[jpos.x][jpos.y]);
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的coj_1224: ACM小组的古怪象棋的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。