嵊州普及Day1T2
2024-10-08 14:20:19
题意:走迷宫。求走到a[n][n]需要多久。
考场上想的dfs,听老师说最多50分。代码懒得码了,知道是走迷宫就好。
正解:bfs,时间复杂度O(n)。
见代码:
#include<iostream>
using namespace std;
int n,head=,tail=,a[][],h[],l[],t[];
int a1[]={,-,,,},a2[]={,,,-,};
int c1[]={,-,-,,},c2[]={,-,,-,};
int flag[][];
char s;
int main(){
cin>>n;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
cin>>s;
a[i][j]=int(s)-int('A')+;
if(a[i][j]==)
flag[i][j]=0x3f3f3f3f;
}
flag[][]=;
flag[][n]=;
flag[n][]=;
h[]=;
h[]=;
h[]=n;
l[]=;
l[]=n;
l[]=;
while(head!=tail)
{
head++;
int x=h[head],y=l[head];
if(a[x][y]==)
{
for(int i=;i<=;i++)
{
if(x+a1[i]>&&x+a1[i]<=n&&y+a2[i]>&&y+a2[i]<=n)
{
if(flag[x+a1[i]][y+a2[i]]==||flag[x+a1[i]][y+a2[i]]>flag[x][y]+)
tail++;
h[tail]=x+a1[i];
l[tail]=y+a2[i];
flag[x+a1[i]][y+a2[i]]=flag[x][y]+;
}
}
}
if(a[x][y]==)
{
for(int i=;i<=;i++)
{
if(x+a1[i]*>&&x+a1[i]*<=n&&y+a2[i]*>&&y+a2[i]*<=n)
{
if(flag[x+a1[i]*][y+a2[i]*]==||flag[x+a1[i]*][y+a2[i]*]>flag[x][y]+)
tail++;
h[tail]=x+a1[i]*;
l[tail]=y+a2[i]*;
flag[x+a1[i]*][y+a2[i]*]=flag[x][y]+;
}
}
}
if(a[x][y]==)
{
for(int i=;i<=;i++)
{
if(x+c1[i]>&&x+c1[i]<=n&&y+c2[i]>&&y+c2[i]<=n)
{
if(flag[x+c1[i]][y+c2[i]]==||flag[x+c1[i]][y+c2[i]]>flag[x][y]+)
tail++;
h[tail]=x+c1[i];
l[tail]=y+c2[i];
flag[x+c1[i]][y+c2[i]]=flag[x][y]+;
}
}
}
}
if(a[n][n]==)
cout<<"GO to find Marx";
else
cout<<a[n][n];
return ;
}
总而言之,相对简单的普及题。
好题哉!!!
最新文章
- PHP 错误与异常 笔记与总结(7)将错误日志以邮件方式发送
- 【java】 java 实现mysql备份
- .NET类型转换的常用方式
- [ZETCODE]wxWidgets教程一:介紹
- curl之post提交xml
- 动手写个数字输入框1:input[type=number]的遗憾
- java之集合Collection详解之2
- Java web的一些面试题
- JEECG 3.7.8 新版表单校验提示风格使用&;升级方法(validform 新风格漂亮,布局简单)
- 启动tomcat报错com.sun.faces.config.ConfigureListener
- Docker应用:Docker-compose(容器编排)
- 【学亮IT手记】PL/SQL游标编程
- Linux 小记 — Ubuntu 自动化配置
- 使用photoshop以及markman进行快速重构页面的几个步骤
- cf789c
- Introduction to pinatrace annotate version 2: a look into latches again
- jode反编译软件
- GUI编程实例
- jQuery秒表、闹钟、计时器和报警插件
- CodeForces 288C Polo the Penguin and XOR operation (位运算,异或)