前言
然而,当数据达到一定程度,我们使用简单的方法肯定会爆炸的,各种TLE(超时),不分析原因还会一直提交一直TLE。就可能需要一些特殊的巧妙方法处理,比如各种剪枝
、优先队列
、A*
、dfs套bfs
,又或者利用一些非常厉害的数学方法比如康托展开(逆展开)等等。而今天,我们谈谈双向bfs。(通常可以将时间复杂度优化为原时间的根号级别)
bfs又称广度优先搜索
此后再无bfs…
而很多笔试面试还是其他机试其实对bfs的要求远远不止那么低的,需要能够处理一些小问题、写出对应代码。而且bfs
可以处理很多问题,很多dfs搜索能够解决的问题bfs也能解决很多(相反也成立),并且很多跟状态
有些关系的用bfs更好控制,因为bfs借助的是一个队列实现,队列中储存节点就可以保存一些节点的状态。
不过bfs并不是万能的,具体问题要看迷宫的大小的,迷宫长宽没增加一个数,那么这个数量级增加是非常大的,因为搜索次数大概和边长的指数级别有关系。当然这里不详细介绍bfs了,大家可以看以前的一篇文章。数据结构与算法—深度、宽度优先(dfs,bfs)搜索
什么样的情况可以使用双向bfs来优化呢?其实双向bfs的主要思想是问题的拆分吧,比如在一个迷宫中可以往下往右行走,问你有多少种方式从左上到右下。
mid
的总次数为n1
,然后这个mid到(n,n)点的总次数为n2
,然后根据排列组合总次数就是n1*n2
(n1和n2正常差不多大)这样就可以通过乘法减少加法的运算次数啦!n1 * n2
次,如果分成两个部分相乘那就是n1+n2
次。两者差距如果n1,n2=1000左右,那么这么一次差距是平方(根号)级别的。从搜索图形来看其实这么一次搜索是本来一个n*n大小
的搜索转变成n次(每次大概是(n/2) * (n/2)
大小的迷宫搜索两次)。也就是如果18*18的迷宫如果使用直接搜索,那么大概2^18
次方量级,而如果采用双向bfs,那么就是2^9
这个量级。题目链接:http://oj.hzjingma.com/contest/problem?id=20&pid=8#problem-anchor
分析:对于题目的要求还是很容易理解的,就是找到所有的路径种类,再判断其中是对称路径的有几个输出即可!
对于一个普通思考是这样的,首先是进行dfs,然后动态维护一个字符串,每次跑到最后判断这个路径字符串是否满足对称要求,如果满足那么就添加到容器中进行判断。可惜很遗憾这样是超时的,仅能通过40%的样例。
接着用普通bfs进行尝试,维护一个node节点,每次走的时候路径储存起来其实这个效率跟dfs差不多依然超时。只能通过40%数据。
接下来就开始双向bfs进行分析!
n-1 + n
为奇数).(1,1)到对角节点k
(设为k节点)的路径有没有和从(n,n)到k
相同的。如果有路径相同的那么就说明这一对构成对称路径左上到(1,1)
,一次右下到(n,n)
).并且将路径放到两个hashset(set1,set2)中,跑完之后用遍历其中一个hashset中的路径,看看另一个set是否存在该路径,如果存在就说明这个是对称路径放到 总的hashset(set) 中。对角线每个位置都这样判断完最后只需要输出总的hashset(set)的集合大小即可!ac代码如下:
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class test2 {
static class node{
int x;
int y;
String path="";
public node() {}
public node(int x,int y,String team)
{
this.x=x;
this.y=y;
this.path=team;
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
Set<String>set=new HashSet<String>();//储存最终结果
int n=Integer.parseInt(sc.nextLine());
char map[][]=new char[n][n];
for(int i=0;i<n;i++)
{
String string=sc.nextLine();
map[i]=string.toCharArray();
}
Queue<node>q1=new ArrayDeque<node>();//左上的队列
Queue<node>q2=new ArrayDeque<node>();//右下的队列
for(int i=0;i<n;i++)
{
q1.clear();q2.clear();
Set<String>set1=new HashSet<String>();//储存zuoshang
Set<String>set2=new HashSet<String>();//储右下
q1.add(new node(i,n-1-i,""+map[i][n-1-i]));
q2.add(new node(i,n-1-i,""+map[i][n-1-i]));
while(!q1.isEmpty()&&!q2.isEmpty())
{
node team=q1.poll();
node team2=q2.poll();
if(team.x==n-1&&team.y==n-1)//到终点,将路径储存
{
//System.out.println(team2.path);
set1.add(team.path);
set2.add(team2.path);
}
else {
if(team.x<n-1)//可以向下
{
q1.add(new node(team.x+1, team.y, team.path+map[team.x+1][team.y]));
}
if(team.y<n-1)//可以向右
{
q1.add(new node(team.x, team.y+1, team.path+map[team.x][team.y+1]));
}
if(team2.x>0)//上
{
q2.add(new node(team2.x-1, team2.y, team2.path+map[team2.x-1][team2.y]));
}
if(team2.y>0)//左
{
q2.add(new node(team2.x, team2.y-1, team2.path+map[team2.x][team2.y-1]));
}
}
}
for(String va:set1)
{
if(set2.contains(va))
{
set.add(va);
}
}
}
System.out.println(set.size());
}
}