题解 P3395 路障
2024-10-20 11:41:59
前言
没想到这是\(\sf {tgD1T1}\)难度……
题目大意
有一个\(n\times n\) 的棋盘,有\(2n-2\) 个路障,在第\(i\) 秒会在\((x_i,y_i)\) 放置路障。求B君是否能从\((1,1)\) 走到\((n,n)\) 。
\(\sf Solution\)
模拟+bfs。
从起点开始,边走边放置路障。碰到路障就不继续走,找到一条路径就标记并break 。若搜完整个棋盘仍未找到路径,输出No
,否则Yes
。
\(\sf {P.S.}\)
注意放置路障后该位置永久无法通行。如果只是单纯的判断,是会WA+MLE的……
\(\sf {Code}\)
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int t,n,a[2001],b[2001],xx,yy,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool vis[1001][1001],flag;
struct node
{
int x,y,k;
} o;
queue<node>q;
int main()
{
scanf("%d",&t);
while(t--)
{
while(!q.empty())
q.pop();
memset(vis,0,sizeof(vis));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
vis[1][1]=true;flag=false;//初始化
scanf("%d",&n);
for(int i=1;i<=2*n-2;++i)
scanf("%d%d",&a[i],&b[i]);//读入
q.push((node){1,1,0});//入队
while(!q.empty())//bfs
{
o=q.front(),q.pop();
if(o.x==n&&o.y==n)//找到路径
{
printf("Yes\n");
flag=true;//标记
break;
}
vis[a[o.k-1]][b[o.k-1]]=1;//放置路障
for(int i=0;i<4;++i)
{
xx=o.x+dx[i],yy=o.y+dy[i];
if(xx<=0||yy<=0||xx>n||yy>n||vis[xx][yy]||a[o.k]==o.x&&b[o.k]==o.y)
continue;//判断不合法情况
vis[xx][yy]=true;q.push((node){xx,yy,o.k+1});//标记为已走并入队
}
}
if(flag==false)
printf("No\n");//未找到路径,输出No
}
return 0;
}
最新文章
- UNIX文件的权限之“设置用户ID位”
- UWP 解决Webview在Pivot里面无法左右滑动的问题
- 写简单游戏,学编程语言-python篇:大鱼吃小鱼
- QTableView 添加进度条
- 【xsy1230】树
- Oracle 11g RAC 第二节点root.sh执行失败后再次执行root.sh
- SQL Server 基础 之 GROUP BY子句
- Android webkit 事件传递流程详解
- Fragstats景观分析研究
- PHP中的循环while、do...while、for、foreach四种循环。
- mongodb数据库备份迁移 windows ->; linux
- Swift基础之CoreData的使用
- Ubuntu12.04下安装NS3.25
- C语言面试题分类->;位运算
- 远程过程调用(RPC)
- Nginx模块开发与架构解析(nginx安装、配置说明)
- Failure to transfer org.apache.maven.plugins:maven-surefire-plugin:pom:2.12.4
- threading模块小结
- LabVIEW(十二):VI本地化-控件标题内容的修改
- 【Java】分布式RPC通信框架Apache Thrift 使用总结