Responsive image

问题 D: 这是一道思维题

问题 D: 这是一道思维题

时间限制: 1 Sec  内存限制: 128 MB
提交: 152  解决: 44
[提交][状态][讨论版][命题人:]

题目描述

在很久很久以前,青蛙王子orange和公主apple因爱相恋,并且两人在偏远的桃花村里一直过着幸福的生活.......

但是就在前几天,双十一的晚上,apple突然着了双十一的道了,她发现了好多好多好吃的都是买一送一,于是她买了朱爹地手工小麻花、三只老鼠大礼包、张二嘎瓜子........此时orange还在熟睡中,然后她又下了一个老奶奶花生米的单,她看到orange的手机一直在闪,走近之后她发现自己刷爆了orange的银行卡,完蛋了完蛋了,刚刚一直沉浸在下单的快乐中,apple害怕orange早上起来会疯掉,于是决定半夜出门捡钱,第二天存到orange的卡里,就在apple刚出门的时候,天上突然掉下来一块馅饼,上面写着:有缘人,是上天让我们相遇,我要告诉你一个秘密,在不远处的洪荒之地有个宝藏,地图就在下面,快去吧。于是......实在bian不下去了.

简言之,一个 n×n 的地图,Apple站在 (1,1) 位置,宝藏在在 (n,n)B的 位置,迷宫中会有障碍物,规定障碍物在迷宫中不能同行且不能同列。apple只能在地图中移动且不能跨越障碍物,每次只能移动一个格子且只有上下左右四个方向。
apple能成功得到宝藏吗?若能输出 Yes,并输出最少所用步数.否则输出 No.
如图所示,A 代表apple,B 代表宝藏,# 代表障碍物,箭头代表移动的四个方向:


输入描述

第一行一个整数 T,代表 T 组测试数据.
对于每一组数据,第一行两个整数 n 和 m,分别表示 n×n 迷宫大小和 m 个障碍物,接下来 m 行,每一行两个整数 x 和 y,表示障碍物坐标 (x,y)
数据保证障碍物不同行且不同列,且不在位置 (1,1),(n,n)
(1≤T≤2000,1≤m,n≤10000,1≤x,y≤n)

输出描述

对于每组测试样例,输出占一行。
若成功解救输出 Yes,并输出最少所用步数.否则输出 No 。

样例输入

2
2 1
1 2
2 2
1 2
2 1

样例输出

Yes 2
No

提示

这真的是一道思维题,俺发4,

[提交][状态]
ACM算法攻关部