在国际象棋里, 王是最重要的一个棋子. 每一步, 王可以往上下左右或者对角线方向移动一步, 如下图所示
给定两个格子 A(r1c1) B(r2c2), 你的任务是计算出一个王从 A 到 B 至少需要走多少步. 为了避免题目太简单, 我们从棋盘里拿掉了一个格子 C(r3c3)(ABC 保证互不相同), 要求王从 A 走到 B 的过程中不能进入格子 C. 在本题中, 各行从上到下编号为 1~8, 各列从左到右编号为 1~8.
Input
输入包含不超过 10000 组数据. 每组数据包含 6 个整数 r1 c1 r2 c2 r3 c3 (1<=r1 c1 r2 c2 r3c3<=8). 三个格子 A B C 保证各不相同.
Output
对于每组数据, 输出测试点编号和最少步数.
- Sample Input
- copy
- 1 1 8 7 5 6
- 1 1 3 3 2 2
- Sample Output
- copy
- Case 1: 7
- Case 2: 3
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- #include <string>
- #include <cstring>
- #include <cstdlib>
- #include <map>
- #include <vector>
- #include <set>
- #include <queue>
- #include <stack>
- #include <cmath>
- #define lli long long
- #define mem(s,t) memset(s,t,sizeof(s))
- #define ok return 0;
- #define rep(x) for(int i=0;i<x;i++) cin>>a[i];
- #define TLE std::iOS::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
- using namespace std;
- int num[51 ];
- int dir[8][2] = {1,0,-1,0, 0,1,0,-1, 1,1,1,-1, -1,1,-1,-1};
- struct node
- {
- int x,y,t;
- };
- node a,b,c;
- int vis[9][9];
- void debug()
- {
- for(int i=0; i<=8; i++)
- {
- for(int j=0; j<=8; j++)
- cout<<vis[i][j];
- cout<<endl;
- }
- }
- void BFS()
- {
- queue<node>q;
- node now,nx;
- q.push(a);
- while(!q.empty())
- {
- now = q.front();
- q.pop();
- if(now.x==b.x && now.y==b.y)
- break;
- for(int i=0; i<8; i++)
- {
- nx.x=now.x+dir[i][0];
- nx.y=now.y+dir[i][1];
- nx.t=now.t+1;
- if(nx.x<1 || nx.y<1 || nx.x>8|| nx.y>8) continue;
- if(!vis[nx.x][nx.y] )
- {
- q.push(nx);
- vis[nx.x][nx.y] = 1 ;
- }
- }
- }
- cout<<now.t<<endl;
- }
- int main()
- {
- int tt=1;
- while(cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y)
- {
- a.t=0;
- mem(vis,0);
- vis[c.x][c.y]=1;
- vis[a.x][a.y]=1;
- cout<<"Case"<<tt++<<":";
- BFS();
- }
- }
来源: http://www.bubuko.com/infodetail-3210530.html