洛谷 U138573 序章&第一章 黑暗时代（eviltime）
题目背景
“博士，你醒了。”
“抓住我的手”
“你还能回忆起自己的名字吗”
“不能吗……这样啊……”
“欢迎回来，Dr.不能”
“欢迎回来，Dr.qwq”
题目描述
游戏中，玩家扮演的是一个因故失忆的博士（刀客塔）。
你被困在了敌人曾经的老巢——切尔诺伯格，而现在的任务则是逃出来，回到你属于的罗德岛
切城的道路错综复杂，大体形成了一个网状的结构。
每两条路的交叉点叫做一个节点，而所有的边交叉在一起便形成了一个 n * mn∗m 的矩阵
而现在，在天灾的作用下，每秒钟都会有节点被摧毁。节点被摧毁后将会无法通行。
为了更高效地撤离，随行的术士算出了每个节点将要被摧毁的时间。Amiya告诉你，你曾是泰拉世界在研究矿石病方面最权威的专家——你也曾多次带着自己的小队突破那一道道看似不可能突破的难关……
而这一次，你能成功吗？
输入格式
第一行两个整数NN MM表示切城的道路大体上可以描述成一个NMN∗M*的矩阵
接下来NN行，每行MM个整数，表示节点会在第a_{i,j}a**i,j分钟被摧毁
特别地，若当前节点的值为0，则代表它早已被摧毁。
输出格式
一行，小队通过的最短时间。若无法通过，输出“N0”（不包含引号）。
题解：
SB题，SB人，超级SB出题人
经典宽搜。
坑点很多，包括但不完全是：
N0而非No。
代码：
#include<cstdio>
#include<queue>
#define int long long
using namespace std;
char *p1,*p2,buf[100000];
#define nc() getchar()
int read()
{
int x=0,f=1;
char ch=nc();
while(ch<48||ch>57)
if(ch=='-')
f=-1,ch=nc();
while(ch>=48&&ch<=57)
x=x*10+ch-48,ch=nc();
return x*f;
}
const int maxn=1e4+10;
const int maxm=1010;
int n,m;
int a[maxn][maxm];
bool vis[maxn][maxm];
int dx[]={0,0,0,-1,1};
int dy[]={0,1,-1,0,0};
struct node
{
int x,y,d;
};
queue<node> q;
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%lld",&a[i][j]);
if(a[n][m]<=0)
{
puts("N0");
return 0;
}
node b;
b.x=n;b.y=m;b.d=0;vis[n][m]=1;
q.push(b);
while(!q.empty())
{
node u=q.front();
q.pop();
if(u.x==1 && u.y==1)
{
printf("%lld
",u.d);
return 0;
}
node v;
for(int i=1;i<=4;i++)
{
int xx=u.x+dx[i];
int yy=u.y+dy[i];
int dd=u.d+1;
if(xx<1 || yy<1 || xx>n || yy>m || vis[xx][yy] || dd>=a[xx][yy])
continue;
v.x=xx;
v.y=yy;
v.d=dd;
q.push(v);
vis[xx][yy]=1;
}
}
puts("N0");
return 0;
}