@[Hzh114514](/user/1054021) 空间超出限制
by DFs_YYDS @ 2024-03-20 13:40:40
@[Hzh114514](/user/1054021) 有可能是数组定义太大或递归层数太多
by DFs_YYDS @ 2024-03-20 13:41:17
能帮忙看下吗
by Hzh114514 @ 2024-03-20 13:44:50
```cpp
/*
路障：
题目分析：
1 输入 T 组数据 每组数据有地图大小 每个路障的行下标和列下标
2 B 君每次走一步后 x y 的地方放下一个路障
3 如果 B 君能走到 n n 输出 Yes 否则输出 No
思路分析：
1 输入 T 表示有 T 组数据
1 循环 T 次输入每组地图的大小 n
1 循环 2n-2 次输入每个路障的行列下标 x 和 y
2 将二号地图的路障位置标记为当前路障落下时间(i) 其他地方初始化为 2n-1
2 调用 dfs 函数
2 声明 dfs 函数
1 标记当前位置
2 把当前位置入队
1 标记队首元素
2 队首出队
3 如果到达终点输出 Yes 并 结束函数
4 遍历四个方向
1 计算出下一个位置
2 越界判断
3 如果现在位置的层数 < 路障落下的时间 并且没有走过
1 把当前位置入队
2 把当前位置标记
3 计算层数并存下来
3 输出 No
*/
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x,y,step;
}t,u;
queue <node> q;
int T,n,x,y;
int map1[1005][1005];
int map2[1005][1005];
bool book[1005][1005];
int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
void bfs(int x,int y)
{
book[x][y]=1;
t.x=x;
t.y=y;
t.step=0;
q.push(t);
while(!q.empty())
{
t=q.front();
q.pop();
if(t.x==n && t.y==n)
{
cout << "Yes" << endl;
return;
}
for(int i=0;i<4;i++)
{
int nx=t.x+d[i][0];
int ny=t.y+d[i][1];
if(nx>n || nx<1 || ny>n || ny<1) continue;
if(map2[nx][ny]<map1[nx][ny])
{
u.x=nx;
u.y=ny;
u.step=t.step+1;
book[nx][ny]=1;
q.push(u);
}
}
}
cout << "No" << endl;
}
int main()
{
cin >> T;
for(int i=1;i<=T;i++)
{
cin >> n;
memset(map1,2*n-1,sizeof(map1));
memset(map2,0,sizeof(map2));
memset(book,0,sizeof(book));
for(int j=1;j<=2*n-2;j++)
{
cin >> x >> y;
map1[x][y]=i;
}
bfs(1,1);
}
return 0;
}
```
by Hzh114514 @ 2024-03-20 13:46:33
又没有递归
空间也是按题目来的
by Hzh114514 @ 2024-03-20 13:47:42
@[Hzh114514](/user/1054021) bdfs at memset
by IOI_ILJYT @ 2024-03-20 14:16:23
@[Hzh114514](/user/1054021) 队列有可能太大了，又有三个$1005^{2}$的数组
by monkeyinGD @ 2024-03-20 19:27:55
@[Hzh114514](/user/1054021) map1的memset也有问题
by monkeyinGD @ 2024-03-20 19:28:42
@[Hzh114514](/user/1054021) 你没有判重。
验证码mlep祭
by incra @ 2024-03-20 21:07:04