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

约定不等于承诺〃 2022-02-24 02:36 243阅读 0赞

题目链接：[https://www.hpuoj.com/contest/16/problem/C/][https_www.hpuoj.com_contest_16_problem_C]

### Problem Description： ###

**单测试点时限:** 1.0 秒

**内存限制:** 512 MB

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

![2019.ePyGjYij.PNG][]

### Input： ###

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

### Output： ###

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

### Sample Input： ###

2  
2 1  
1 2  
2 2  
1 2  
2 1

### Sample Output： ###

Yes 2  
No

思路：被这道题套路了，掉进了bfs的坑里无法自拔。其实这道题压根儿就没用到bfs的知识点，题目上一个最重要的一句话被我选择性忽略了，**障碍物在迷宫中不能同行且不能同列**，（没错，这就是欺骗我感情的15个字儿，我算是记住你了），所以按最优解的情况，只要障碍物不是在斜着的一排上都可以到达终点，而且最少步数是 2\*n-2 步

（因为障碍物只可能在当前位置的右边和下边其中一个，当然也可能是左边或上边，但为了使步数最少，不会往回走，所以这种情况就不考虑了，因此若障碍物在右边就走下边，若在下边就走右边，无论是哪种情况，步数都是1，所以最少步数就是2\*n-2步）

接着就是如何判断障碍物是不是在斜着的一排上，当 x1+y1=x2+y2时，这两个格子在同一斜线。

### My Code： ###

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<queue>
    #include<math.h>
    #include<set>
    using namespace std;
    #define INF 1e9
    typedef long long ll;
    
    const int MOD = (int)1e9 + 7;
    
    int main() {
    
        int t;
        cin >> t;
        while(t--)
        {
            int n,m;
            scanf("%d%d",&n,&m);
            int x[10005],y[10005],k=0;
            for(int i = 0; i < m; i++)
            {
                scanf("%d%d",&x[i],&y[i]);
                if(i > 0)
                {
                    if(x[i]+y[i] != x[0] + y[0])
                        k = 1;
                }
            }
            if(k == 0 && m > 1 && m == x[0]+y[0]-1)
                printf("No\n");
            else printf("Yes %d\n",2*n-2);
        }
        
    	return 0;
    }

[https_www.hpuoj.com_contest_16_problem_C]: https://www.hpuoj.com/contest/16/problem/C/
[2019.ePyGjYij.PNG]: https://www.hpuoj.com/upload/173/2019.ePyGjYij.PNG