题意:走迷宫。求走到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 ;
}

总而言之,相对简单的普及题。

好题哉!!!

最新文章

  1. PHP 错误与异常 笔记与总结(7)将错误日志以邮件方式发送
  2. 【java】 java 实现mysql备份
  3. .NET类型转换的常用方式
  4. [ZETCODE]wxWidgets教程一:介紹
  5. curl之post提交xml
  6. 动手写个数字输入框1:input[type=number]的遗憾
  7. java之集合Collection详解之2
  8. Java web的一些面试题
  9. JEECG 3.7.8 新版表单校验提示风格使用&amp;升级方法(validform 新风格漂亮,布局简单)
  10. 启动tomcat报错com.sun.faces.config.ConfigureListener
  11. Docker应用:Docker-compose(容器编排)
  12. 【学亮IT手记】PL/SQL游标编程
  13. Linux 小记 — Ubuntu 自动化配置
  14. 使用photoshop以及markman进行快速重构页面的几个步骤
  15. cf789c
  16. Introduction to pinatrace annotate version 2: a look into latches again
  17. jode反编译软件
  18. GUI编程实例
  19. jQuery秒表、闹钟、计时器和报警插件
  20. CodeForces 288C Polo the Penguin and XOR operation (位运算,异或)

热门文章

  1. 模块学习--random
  2. nginx的access的阶段的access模块、auth_basic模块、auth_request模块及satisfy指令介绍
  3. Celeste 机制研究
  4. core版本使用ef连接数据库(一)
  5. UISearchBar设置背景色
  6. mabatisplus-update
  7. 1 Oracle概述&amp;与MySQL的差别&amp;SQL语句分类复习
  8. sentinel控制台
  9. DatePicker和DatePickerDialog的使用
  10. 原生JS获取所有标签的数量并统计每个标签的数量