题目链接：https://www.hpuoj.com/contest/16/problem/C/
题目中有一句很重要的话：规定障碍物在迷宫中不能同行且不能同列，
这就表明只要障碍物不是在斜对角线中，那么就一定会有路到，并且最短为2*n-2;
只要不是这种斜对角线就行，我们数组从0开始编号，从左到右每条对角线上的数目多1.
我们只要考虑这种情况就可以了。
| A | X | |||
| X | ||||
| X | ||||
| B |
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int maxn=100000+10; int a[maxn]; int main() { int t,n,m,x,y; cin >> t; while (t--) { memset(a,0,sizeof(a)); cin >> n >> m; int flag = 0; while (m--) { cin >> x >> y; x--,y--; a[n+x+y]++; if (x+y < n) { if (a[n+x+y] == x+y+1) flag = 1; } else { if (a[n+x+y] == n*2-1-x-y) flag = 1; } } if (flag == 0) printf("Yes %d\n",n*2-2); else printf("No\n"); } return 0; }
原文：https://www.cnblogs.com/SJCHEN/p/10637768.html