Codeforces Round 217 (Div. 2) A. Rook, Bishop and King(BFS)

2024-05-11 01:12

本文主要是介绍Codeforces Round 217 (Div. 2) A. Rook, Bishop and King(BFS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Rook, Bishop and King

题面翻译

【题目描述】

佩蒂亚正在学习国际象棋。他已经学会如何移动王、车和象。让我们提示你如何移动国象棋子。棋盘有 64 64 64个棋格,呈 8 × 8 8\times8 8×8正方形。一个格子可以用 ( r , c ) (r,c) (r,c)来表示—— r r r指行, c c c指列(虽然在经典棋局中用字母和数字一起表示)。每一个棋子占用一个棋格。一次合法的棋步就是执行如下之一:

  • 车可以横向或纵向移动任意格。
  • 象可以斜着移动任意格。
  • 王可以任意方向移动一格——横着或者斜着。

佩蒂亚在想,从 ( r 1 , c 1 ) (r_1,c_1) (r1,c1)移动到 ( r 2 , c 2 ) (r_2,c_2) (r2,c2)所需的最少步数是多少?我们假设在棋盘上只有一枚棋子。帮他解决问题。

【输入格式】

输入包括四个整数 r 1 , c 1 , r 2 , c 2 ( 1 < = r 1 , c 1 , r 2 , c 2 < = 8 ) r_1,c_1,r_2,c_2(1<=r_1,c_1,r_2,c_2<=8) r1,c1,r2,c2(1<=r1,c1,r2,c2<=8)——分别代表出发的棋格和目的地棋格。数据保证两个格子不相同。你可以假设棋盘的行从上到下是 1 1 1 8 8 8,棋盘从左到右是 1 1 1 8 8 8

【输出格式】

输出三个用空格分隔的整数,分别代表车、象、王从 ( r 1 , c 1 ) (r_1,c_1) (r1,c1)移动到 ( r 2 , c 2 ) (r_2,c_2) (r2,c2)所需的最少步数。如果无法移动到,则输出 0 0 0

题目描述

Little Petya is learning to play chess. He has already learned how to move a king, a rook and a bishop. Let us remind you the rules of moving chess pieces. A chessboard is 64 square fields organized into an $ 8×8 $ table. A field is represented by a pair of integers $ (r,c) $ — the number of the row and the number of the column (in a classical game the columns are traditionally indexed by letters). Each chess piece takes up exactly one field. To make a move is to move a chess piece, the pieces move by the following rules:

  • A rook moves any number of fields horizontally or vertically.
  • A bishop moves any number of fields diagonally.
  • A king moves one field in any direction — horizontally, vertically or diagonally.

The pieces move like thatPetya is thinking about the following problem: what minimum number of moves is needed for each of these pieces to move from field $ (r_{1},c_{1}) $ to field $ (r_{2},c_{2}) $ ? At that, we assume that there are no more pieces besides this one on the board. Help him solve this problem.

输入格式

The input contains four integers $ r_{1},c_{1},r_{2},c_{2} $ ( $ 1<=r_{1},c_{1},r_{2},c_{2}<=8 $ ) — the coordinates of the starting and the final field. The starting field doesn’t coincide with the final one.

You can assume that the chessboard rows are numbered from top to bottom 1 through 8, and the columns are numbered from left to right 1 through 8.

输出格式

Print three space-separated integers: the minimum number of moves the rook, the bishop and the king (in this order) is needed to move from field $ (r_{1},c_{1}) $ to field $ (r_{2},c_{2}) $ . If a piece cannot make such a move, print a 0 instead of the corresponding number.

样例 #1

样例输入 #1

4 3 1 6

样例输出 #1

2 1 3

样例 #2

样例输入 #2

5 5 5 6

样例输出 #2

1 0 1

这道题和普通的BFS并无太大区别,在做的时候我会想到开一个结构体来记录坐标,步数和前一步操作,这个方法对于Rook和King都适用,但是对Bishop不行

Bishop的移动过程是斜着移动多个距离,如果一个一个坐标的进行遍历,就会导致有些坐标会被封堵上,这样就导致有些情况是无法被扫出来的。

所以这道题BFS的正解其实是每次都遍历完路径上能够到达的所有点。

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N = 15;
const int Rook_dx[4] = {1,-1,0,0};
const int Rook_dy[4] = {0,0,1,-1};
const int Bishop_dx[4] = {1,1,-1,-1};
const int Bishop_dy[4] = {1,-1,1,-1};
const int King_dx[8] = {1,0,-1,0,1,1,-1,-1};
const int King_dy[8] = {0,1,0,-1,1,-1,1,-1};
struct Node{int x,y;int step;int pre;
};
int r1,c1,r2,c2;
bool vis[N][N];int bfs(int type){ //1:Rook,2"Bishop,3"Kingmemset(vis,0,sizeof vis);int res = 2e9;queue<Node>q;q.push({r1,c1,0,10});vis[r1][c1] = 1;while(q.size()){Node t = q.front();q.pop();if(t.x == r2 && t.y == c2)return t.step;//cout << t.x << " " << t.y << " " << t.step << endl;if(type == 1){for(int i = 0;i < 4;i++){int x = t.x + Rook_dx[i],y = t.y + Rook_dy[i];if(x >= 1 && x <= 8 && y >= 1 && y <= 8 && !vis[x][y]){vis[x][y] = 1;if(t.pre == i) q.push({x,y,t.step,i});else q.push({x,y,t.step + 1,i});}}}else if(type == 2){for(int i = 0;i < 4;i++){int x = t.x,y = t.y;while(x <= 8 && x >= 1 && y <= 8 && y >= 1){	//在没有超过边界的时候一直去走if(!vis[x][y]){q.push({x,y,t.step + 1,i});vis[x][y] = 1;}x += Bishop_dx[i],y += Bishop_dy[i];}}}else{for(int i = 0;i < 8;i++){int x = t.x + King_dx[i],y = t.y + King_dy[i];if(x >= 1 && x <= 8 && y >= 1 && y <= 8 && !vis[x][y]){vis[x][y] = 1;q.push({x,y,t.step + 1,i});}}}}if(res == 2e9)return 0;else return res;
}int main(){cin >> r1 >> c1 >> r2 >> c2;//bfs(2);cout << bfs(1) << " " << bfs(2) << " " << bfs(3) << " ";return 0;
}

这篇关于Codeforces Round 217 (Div. 2) A. Rook, Bishop and King(BFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/978084

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor