CF1033A King Escape 题解 思维

2024-02-04 06:44

本文主要是介绍CF1033A King Escape 题解 思维,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

King Escape

传送门

Alice and Bob are playing chess on a huge chessboard with dimensions n × n n \times n n×n. Alice has a single piece left — a queen, located at ( a x , a y ) (a_x, a_y) (ax,ay), while Bob has only the king standing at ( b x , b y ) (b_x, b_y) (bx,by). Alice thinks that as her queen is dominating the chessboard, victory is hers.

But Bob has made a devious plan to seize the victory for himself — he needs to march his king to ( c x , c y ) (c_x, c_y) (cx,cy) in order to claim the victory for himself. As Alice is distracted by her sense of superiority, she no longer moves any pieces around, and it is only Bob who makes any turns.

Bob will win if he can move his king from ( b x , b y ) (b_x, b_y) (bx,by) to ( c x , c y ) (c_x, c_y) (cx,cy) without ever getting in check. Remember that a king can move to any of the 8 8 8 adjacent squares. A king is in check if it is on the same rank (i.e. row), file (i.e. column), or diagonal as the enemy queen.

Find whether Bob can win or not.

Input

The first line contains a single integer n n n ( 3 ≤ n ≤ 1000 3 \leq n \leq 1000 3n1000) — the dimensions of the chessboard.

The second line contains two integers a x a_x ax and a y a_y ay ( 1 ≤ a x , a y ≤ n 1 \leq a_x, a_y \leq n 1ax,ayn) — the coordinates of Alice’s queen.

The third line contains two integers b x b_x bx and b y b_y by ( 1 ≤ b x , b y ≤ n 1 \leq b_x, b_y \leq n 1bx,byn) — the coordinates of Bob’s king.

The fourth line contains two integers c x c_x cx and c y c_y cy ( 1 ≤ c x , c y ≤ n 1 \leq c_x, c_y \leq n 1cx,cyn) — the coordinates of the location that Bob wants to get to.

It is guaranteed that Bob’s king is currently not in check and the target location is not in check either.

Furthermore, the king is not located on the same square as the queen (i.e. a x ≠ b x a_x \neq b_x ax=bx or a y ≠ b y a_y \neq b_y ay=by), and the target does coincide neither with the queen’s position (i.e. c x ≠ a x c_x \neq a_x cx=ax or c y ≠ a y c_y \neq a_y cy=ay) nor with the king’s position (i.e. c x ≠ b x c_x \neq b_x cx=bx or c y ≠ b y c_y \neq b_y cy=by).

Output

Print “YES” (without quotes) if Bob can get from ( b x , b y ) (b_x, b_y) (bx,by) to ( c x , c y ) (c_x, c_y) (cx,cy) without ever getting in check, otherwise print “NO”.

You can print each letter in any case (upper or lower).

Examples

input #1

8
4 4
1 3
3 1

output #1

YES

input #2

8
4 4
2 3
1 6

output #2

NO

input #3

8
3 5
1 2
6 1

output #3

NO

Note

In the diagrams below, the squares controlled by the black queen are marked red, and the target square is marked blue.

In the first case, the king can move, for instance, via the squares ( 2 , 3 ) (2, 3) (2,3) and ( 3 , 2 ) (3, 2) (3,2). Note that the direct route through ( 2 , 2 ) (2, 2) (2,2) goes through check.

In the second case, the queen watches the fourth rank, and the king has no means of crossing it.

In the third case, the queen watches the third file.

题目TM翻译

爱丽丝和鲍勃正在一个尺寸为 n × n n \times n n×n 的巨大棋盘上下棋。爱丽丝只剩下一个棋子–位于 ( a x , a y ) (a_x, a_y) (ax,ay) 的皇后,而鲍勃只有位于 ( b x , b y ) (b_x, b_y) (bx,by) 的国王。爱丽丝认为她的皇后在棋盘上占据优势,胜利属于她。

但鲍勃却制定了一个狡猾的计划来为自己夺取胜利–他需要将国王行进到 ( c x , c y ) (c_x, c_y) (cx,cy) 处,以便为自己赢得胜利。由于爱丽丝被自己的优越感分散了注意力,她不再移动任何棋子,只有鲍勃在行动

如果鲍勃能将国王从 ( b x , b y ) (b_x, b_y) (bx,by) 移动到 ( c x , c y ) (c_x, c_y) (cx,cy) ,那么他就赢了。鲍勃如果能将王从 ( b x , b y ) (b_x, b_y) (bx,by) 移动到 ( c x , c y ) (c_x, c_y) (cx,cy)而不被牵制,他就赢了。记住,国王可以移动到 8 8 8 个相邻位置中的任何一个。如果国王与敌方王后位于同一等级(即行)、文件(即列)或对角线上,国王就会被牵制。

找出鲍勃能否获胜。

输入格式

第一行包含一个整数 n n n ( 3 ≤ n ≤ 1000 3 \leq n \leq 1000 3n1000 ) - 棋盘的尺寸。

第二行包含两个整数 a x a_x ax a y a_y ay 1 ≤ a x , a y ≤ n 1 \leq a_x, a_y \leq n 1ax,ayn )–爱丽丝皇后的坐标。

第三行包含两个整数 b x b_x bx b y b_y by ( 1 ≤ b x , b y ≤ n 1 \leq b_x, b_y \leq n 1bx,byn ) --鲍勃的国王坐标。

第四行包含两个整数 c x c_x cx c y c_y cy --鲍勃的国王坐标。( 1 ≤ c x , c y ≤ n 1 \leq c_x, c_y \leq n 1cx,cyn ) --鲍勃想要到达的位置的坐标。

**保证鲍勃的王目前没有被吃掉,目标位置也没有被吃掉。

此外,国王与王后不在同一位置(即 a x ≠ b x a_x \neq b_x ax=bx a y ≠ b y a_y \neq b_y ay=by ),而目标位置既不与王后的位置(即 c x ≠ a x c_x \neq a_x cx=ax c y ≠ a y c_y \neq a_y cy=ay )重合,也不与国王的位置(即 c x ≠ b x c_x \neq b_x cx=bx c y ≠ b y c_y \neq b_y cy=by )重合。

输出格式

如果鲍勃能从 ( b x , b y ) (b_x, b_y) (bx,by) 到达 ( c x , c y ) (c_x, c_y) (cx,cy) 而不被检查到,则打印 “是”(不带引号),否则打印 “否”。

您可以用任何大小写(大写或小写)打印每个字母。

提示

在下图中,由黑色皇后控制的方格标记为红色,目标方格标记为蓝色。

例如,在第一种情况下,国王可以通过 ( 2 , 3 ) (2, 3) (2,3) ( 3 , 2 ) (3, 2) (3,2) 这两个位置移动。请注意,通过 ( 2 , 2 ) (2, 2) (2,2) 的直接路线要经过格。

在第二种情况下,王后监视着第四位,国王没有办法越过它。

在第三种情况下,王后监视第三列。

以上来自 C o d e F o r c e s ,翻译: D e e p L 以上来自CodeForces,翻译:DeepL 以上来自CodeForces,翻译:DeepL

解题思路

前言

你英语好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?好吗?

正文

想象一个二维平面,原点位于黑皇后的位置。我们注意到皇后将棋盘分割为多达四个连通分量,其中每个象限都是一个分量。因此,当且仅当原国王位置和目标位置位于同一个象限时,答案为“YES”。只要使用特判即可。

什么?你 dfs ⁡ \operatorname{dfs} dfs 写过了?那你看什么题解。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define EX exit(0);
int n, ax, ay, bx, by, cx, cy;
inline bool check(int ax, int ay, int bx, int by, int cx, int cy);
inline void work() {cin >> n >> ax >> ay >> bx >> by >> cx >> cy;if (check(ax, ay, bx, by, cx, cy))puts("YES"), EXputs("NO");
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);work();return 0;
}
inline bool check(int ax, int ay, int bx, int by, int cx, int cy) {return (bx < ax && by < ay && cx < ax && cy < ay) || (bx > ax && by < ay && cx > ax && cy < ay) || (bx < ax && by > ay && cx < ax && cy > ay) || (bx > ax && by > ay && cx > ax && cy > ay);
}

这篇关于CF1033A King Escape 题解 思维的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

颠覆你的开发模式:敏捷思维带来的无限可能

敏捷软件开发作为现代软件工程的重要方法论,强调快速响应变化和持续交付价值。通过灵活的开发模式和高效的团队协作,敏捷方法在应对动态变化和不确定性方面表现出色。本文将结合学习和分析,探讨系统变化对敏捷开发的影响、业务与技术的对齐以及敏捷方法如何在产品开发过程中处理持续变化和迭代。 系统变化对敏捷软件开发的影响 在敏捷软件开发中,系统变化的管理至关重要。系统变化可以是需求的改变、技术的升级、

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

P2858 [USACO06FEB] Treats for the Cows G/S 题解

P2858 题意 给一个数组。每天把最左或者最右的东西卖掉,第 i i i个东西,第 d a y day day天卖出的价格是 a [ i ] ∗ d a y a[i]*day a[i]∗day。 记忆化搜索 void dfs(int l,int r,int day,ll sum){if(v[l][r]>=sum)return;v[l][r]=sum;if(l>r)//这就是dp答案{

【C++题解】1272. 郭远摘苹果

欢迎关注本专栏《C++从零基础到信奥赛入门级(CSP-J)》 问题:1272. 郭远摘苹果 类型:二维数组 题目描述: 郭远有一天走到了一片苹果林,里面每颗树上都结有不同数目的苹果,郭远身上只能拿同一棵树上的苹果,他每到一棵果树前都会把自己身上的苹果扔掉并摘下他所在树上的苹果并带走(假设郭远会走过每一棵苹果树),问在郭远摘苹果的整个过程中,他身上携带的最多苹果数与最小苹果数的差是多少?

【最新华为OD机试E卷-支持在线评测】机器人活动区域(100分)多语言题解-(Python/C/JavaScript/Java/Cpp)

🍭 大家好这里是春秋招笔试突围 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解 💻 ACM金牌🏅️团队| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 🍿 最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测,专栏文章质量平均 94 分 最新华为OD机试目录: https://blog.