第九届河南理工大学算法程序设计大赛正式赛C：Asia区域宫

单测试点时限: 1.0 秒

内存限制: 512 MB

远古洪荒时期，女王Alice和战神Bob因爱相恋，一段催人泪下的爱情故事流传民间.
相传，女王Alice的美貌惊艳六界，作为对颜值颇有要求的上古灵兽Qaq芳心异动，可是女王早已许配给战神Bob，怎么会移情于己呢，而且单挑自己也不是战神Bob的对手。于是，灵兽Qaq便设计将战神Bob引入洪荒之地，种下十里桃花困住战神Bob。女王Alice得知后，冒着渡劫的天雷赶去营救……实在bian不下去了.
简言之，一个 $n\times n$ 的迷宫，Alice站在 $(1,1)$ 位置，Bob被困在 $(n,n)$ 位置，迷宫中会有障碍物，规定障碍物在迷宫中不能同行且不能同列。Alice只能在迷宫中移动且不能跨越障碍物，每次只能移动一个格子且只有上下左右四个方向。
Alice能顺利解救Bob么？若成功解救输出 Yes，并输出最少所用步数.否则输出 No.

如图所示，A 代表Alice，B 代表Bob，# 代表障碍物，箭头代表移动的四个方向：

输入

第一行一个整数 $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 。

样例

input

output

1
2

Yes 2
No

Solve

注意障碍物在迷宫中不能同行且不能同列这句话

所以走不通的情况就转变成了下图红线标注的情况，可以发现这些位置均为$n\times n$方针的对角线，并要有$n$个连续的才可以，所以只需要判断在一条线上的障碍物的个数就可以了

QQ截图20190331212624.png

Code

#include<bits/stdc++.h>
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
const int maxn=1e6+10;
const int maxm=1e4+10;
const int inf=(1<<30);
const ll INF=(1LL*1<<60);
using namespace std;
int vis[maxn];
inline void init()
{
	for(int i=2;i<=maxm;i++)
		vis[i+1]=i;
}
int arr[maxm];
int sum[maxn];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	int t;
	init();
	cin>>t;
	while(t--)
	{
		ms(sum,0);
		int n,m;
		cin>>n>>m;
		int x,y;
		for(int i=0;i<m;i++)
		{
			cin>>x>>y;
			arr[i]=x+y;
			sum[x+y]++;
		}
		sort(arr,arr+m);
		m=unique(arr,arr+m)-arr;
		int flag=0;
		for(int i=0;i<m;i++)
		{
			if(sum[arr[i]]==vis[arr[i]])
			{
				flag=1;
				break;
			}
		}
		if(flag)
			cout<<"No"<<endl;
		else
			cout<<"Yes "<<2*n-2<<endl;
	}
	return 0;
}