1330：【例8.3】最少步數(shù)

時(shí)間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 10314 ??? 通過(guò)數(shù): 5549

【題目描述】

在各種棋中，棋子的走法總是一定的，如中國(guó)象棋中馬走“日”。有一位小學(xué)生就想如果馬能有兩種走法將增加其趣味性，因此，他規(guī)定馬既能按“日”走，也能如象一樣走“田”字。他的同桌平時(shí)喜歡下圍棋，知道這件事后覺得很有趣，就想試一試，在一個(gè)（100×100）的圍棋盤上任選兩點(diǎn)A、B，A點(diǎn)放上黑子，B點(diǎn)放上白子，代表兩匹馬。棋子可以按“日”字走，也可以按“田”字走，倆人一個(gè)走黑馬，一個(gè)走白馬。誰(shuí)用最少的步數(shù)走到左上角坐標(biāo)為(1,1)的點(diǎn)時(shí)，誰(shuí)獲勝?，F(xiàn)在他請(qǐng)你幫忙，給你A、B兩點(diǎn)的坐標(biāo)，想知道兩個(gè)位置到（1,1）點(diǎn)可能的最少步數(shù)。

【輸入】

A、B兩點(diǎn)的坐標(biāo)。

【輸出】

最少步數(shù)。

【輸入樣例】

12 16 18 10

【輸出樣例】

8 9

【分析】

? ? ? ? 馬有 12 種不同的擴(kuò)展方向∶

（1）馬走"日"∶(x-2,y-1)、(x-1,y-2)、(x-2,y+1)、(x-1,y+2)、(x+2,y-1)、(x+1,y-2)、(x+2, y+1)、(x+1,y+2)

（2）馬走"田"：(x-2,y-2)、(x-2.y+2)、(x+2,y-2)、(x+2,y+2)。

表示為：

int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2},
int dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};

【參考代碼】

C代碼：

#include <stdio.h> #include <string.h>int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2}; // 位移數(shù)組 int dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};int main() {int s[101][101]; // 記錄最少步數(shù) int que[10000][4]={0}; // 隊(duì)列數(shù)組，存儲(chǔ)可到達(dá)的點(diǎn) int x1,y1; // 黑馬所在點(diǎn) int x2,y2; // 白馬所在點(diǎn)int head=1,tail=1; // 初始位置入隊(duì)int i;int x,y;memset(s,-1,sizeof(s)); // s數(shù)組的初始化 que[1][1]=1;que[1][2]=1;que[1][3]=0;scanf("%d%d%d%d",&x1,&y1,&x2,&y2); // 讀入黑馬白馬的出發(fā)位置 // bfswhile(head<=tail) // 若隊(duì)列非空，則擴(kuò)展隊(duì)首結(jié)點(diǎn) {for(i=0;i<12;i++) // 枚舉12個(gè)擴(kuò)展方向{x=que[head][1]+dx[i]; // 計(jì)算馬按 i 方向跳躍后的位置 y=que[head][2]+dy[i];if(x>0 && y>0){if(s[x][y]==-1) // 若(x,y)滿足約束條件 {s[x][y]=que[head][3]+1; // 計(jì)算(1,1)到(x,y)的最少步數(shù) tail++; // (1,1)至(x,y)的最少步數(shù)入隊(duì) que[tail][1]=x;que[tail][2]=y;que[tail][3]=s[x][y];if(s[x1][y1]>0 && s[x2][y2]>0) // 輸出問(wèn)題的解 {printf("%d\n%d\n",s[x1][y1],s[x2][y2]);return 0;}}}}head++;}return 0; }

C++代碼：

#include <iostream> #include <queue> #include <cstring>using namespace std;struct node {int x,y; // 坐標(biāo) int step; // 到該結(jié)點(diǎn)的步數(shù) };int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2}; // 位移數(shù)組 int dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};int main() {int a[101][101]; // 記錄最少步數(shù) int que[10000][4]={0}; // 隊(duì)列數(shù)組，存儲(chǔ)可到達(dá)的點(diǎn) int x1,y1; // 黑馬所在點(diǎn) int x2,y2; // 白馬所在點(diǎn) queue <node> q; // 申請(qǐng)隊(duì)列 node start,news;memset(a,-1,sizeof(a)); //a數(shù)組的初始化start.x=1; // 初始化起點(diǎn) start.y=1;start.step=0; q.push(start); // 起始點(diǎn)入隊(duì)cin>>x1>>y1>>x2>>y2; //讀入白馬和黑馬的出發(fā)位置while(!q.empty()) //若隊(duì)列非空，則擴(kuò)展隊(duì)首結(jié)點(diǎn){start=q.front();q.pop();for(int d=0;d<12;d++) //枚舉12個(gè)擴(kuò)展方向{int newx,newy,st;newx=start.x+dx[d]; //計(jì)算馬按d方向跳躍后的位置newy=start.y+dy[d];if(newx>0 && newy>0 && newx<=100 && newy<=100){if(a[newx][newy]==-1) //若（x,y)滿足約束條件{a[newx][newy]=start.step+1; //計(jì)算（1，1）到（x,y）的最少步數(shù)news.x=newx;news.y=newy;news.step=a[newx][newy];q.push(news);if(a[x1][y1]>0 && a[x2][y2]>0) //輸出問(wèn)題的解{cout<<a[x1][y1]<<endl;cout<<a[x2][y2]<<endl;return 0;}}}}}return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1330

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通（1330：【例8.3】最少步数）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。