搜索
框架
dfs框架
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Node {
char value; int lson, rson;
} tree[N]; //tree[0]不用，0表示空结点
int index = 1; //记录结点存在tree[]的位置，从tree[1]开始用
int newNode(char val) { //新建结点
tree[index].value = val;
tree[index].lson = 0; //0表示空，tree[0]不用
tree[index].rson = 0;
return index ++;
}
void insert(int &father, int child, int l_r) { //插入孩子
if (l_r == 0) tree[father].lson = child; //左孩子
else tree[father].rson = child; //右孩子
}
int dfn[N] = {0}; //dfn[i]是结点i的时间戳
int dfn_timer = 0;
void dfn_order (int father) {
if (father != 0) {
dfn[father] = ++dfn_timer;
printf("dfn[%c]=%d; ", tree[father].value, dfn[father]);//打印时间戳
dfn_order (tree[father].lson);
dfn_order (tree[father].rson);
}
}
int visit_timer = 0;
void visit_order (int father) { //打印DFS序
if (father != 0) {
printf("visit[%c]=%d; ", tree[father].value, ++visit_timer);
//打印DFS序：第1次访问结点
visit_order (tree[father].lson);
visit_order (tree[father].rson);
printf("visit[%c]=%d; ", tree[father].value, ++visit_timer);
//打印DFS序：第2次回溯
}
}
int deep[N] = {0}; //deep[i]是结点i的深度
int deep_timer = 0;
void deep_node (int father) {
if (father != 0) {
deep[father] = ++deep_timer; //打印树的深度，第一次访问时，深度+1
printf("deep[%c]=%d; ", tree[father].value, deep[father]);
deep_node (tree[father].lson);
deep_node (tree[father].rson);
deep_timer--; //回溯时，深度-1
}
}
int num[N] = {0}; //num[i]是以i为父亲的子树上的结点总数
int num_node (int father) {
if (father == 0) return 0;
else {
num[father] = num_node (tree[father].lson) +
num_node (tree[father].rson) + 1;
printf("num[%c]=%d; ", tree[father].value, num[father]); //打印数量
return num[father];
}
}
void preorder (int father) { //求先序序列
if (father != 0) {
cout << tree[father].value << " "; //先序输出
preorder (tree[father].lson);
preorder (tree[father].rson);
}
}
void inorder (int father) { //求中序序列
if (father != 0) {
inorder (tree[father].lson);
cout << tree[father].value << " "; //中序输出
inorder (tree[father].rson);
}
}
void postorder (int father) { //求后序序列
if (father != 0) {
postorder (tree[father].lson);
postorder (tree[father].rson);
cout << tree[father].value << " "; //后序输出
}
}
int buildtree() { //建一棵树
int A = newNode('A'); int B = newNode('B'); int C = newNode('C'); //定义结点
int D = newNode('D'); int E = newNode('E'); int F = newNode('F');
int G = newNode('G'); int H = newNode('H'); int I = newNode('I');
insert(E, B, 0); insert(E, G, 1); //建树。E的左孩子是B，右孩子是G
insert(B, A, 0); insert(B, D, 1); insert(G, F, 0); insert(G, I, 1);
insert(D, C, 0); insert(I, H, 0);
int root = E;
return root;
}
int main() {
int root = buildtree();
cout << "dfn order: "; dfn_order(root); cout << endl; //打印时间戳
cout << "visit order: "; visit_order(root); cout << endl; //打印DFS序
cout << "deep order: "; deep_node(root); cout << endl; //打印结点深度
cout << "num of tree: "; num_node(root); cout << endl; //打印子树上的结点数
cout << "in order: "; inorder(root); cout << endl; //打印中序序列
cout << "pre order: "; preorder(root); cout << endl; //打印先序序列
cout << "post order: "; postorder(root); cout << endl; //打印后序序列
return 0;
}
/* 输出是：
dfn order: dfn[E]=1; dfn[B]=2; dfn[A]=3; dfn[D]=4; dfn[C]=5; dfn[G]=6; dfn[F]=7; dfn[I]=8; dfn[H]=9;
visit order: visit[E]=1; visit[B]=2; visit[A]=3; visit[A]=4; visit[D]=5; visit[C]=6; visit[C]=7; visit[D]=8; visit[B]=9; visit[G]=10; visit[F]=11; visit[F]=12; visit[I]=13; visit[H]=14; visit[H]=15; visit[I]=16; visit[G]=17; visit[E]=18;
deep order: deep[E]=1; deep[B]=2; deep[A]=3; deep[D]=3; deep[C]=4; deep[G]=2; deep[F]=3; deep[I]=3; deep[H]=4;
num of tree: num[A]=1; num[C]=1; num[D]=2; num[B]=4; num[F]=1; num[H]=1; num[I]=2; num[G]=4; num[E]=9;
in order: A B C D E F G H I
pre order: E B A D C G F I H
post order: A C D B F H I G E */
bfs框架
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Node { //用静态数组记录二叉树
char value;
int lson, rson; //左右孩子
} tree[N]; //tree[0]不用，0表示空结点
int index = 1; //记录结点存在tree[]的位置，从tree[1]开始用
int newNode(char val) {
tree[index].value = val;
tree[index].lson = 0; //0表示空，tree[0]不用
tree[index].rson = 0;
return index ++;
}
void Insert(int &father, int child, int l_r) { //插入孩子
if (l_r == 0) tree[father].lson = child; //左孩子
else tree[father].rson = child; //右孩子
}
int buildtree() { //建一棵二叉树
int A = newNode('A'); int B = newNode('B'); int C = newNode('C');
int D = newNode('D'); int E = newNode('E'); int F = newNode('F');
int G = newNode('G'); int H = newNode('H'); int I = newNode('I');
Insert(E, B, 0); Insert(E, G, 1); //E的左孩子是B，右孩子是G
Insert(B, A, 0); Insert(B, D, 1);
Insert(G, F, 0); Insert(G, I, 1);
Insert(D, C, 0); Insert(I, H, 0);
int root = E;
return root;
}
int main() {
int root = buildtree();
queue <int> q;
q.push(root); //从根结点开始
while (q.size()) {
int tmp = q.front();
cout << tree[tmp].value << " "; //打印队头
q.pop(); //去掉队头
if (tree[tmp].lson != 0) q.push(tree[tmp].lson); //左孩子入队
if (tree[tmp].rson != 0) q.push(tree[tmp].rson); //右孩子入队
}
return 0;
}
用途
剪枝 记忆化dfs 双向bfs 迭代加dfs A - starbfs IDAdfs
连通性问题
以蓝桥《全球变暖问题》
dfs
const int N;
int mp[N][N];
int vis[N][N];
int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, { -1, 0}};
int flag;
void dfs(int x, int y) {
vis[x][y] = 1;
if ( mp[x][y + 1] == '#' && mp[x][y - 1] == '#' &&
mp[x + 1][y] == '#' && mp[x - 1][y] == '#' )
flag = 1;//有一次能把flag变成一就证明不会被淹没
for (int i = 0; i < 4; i++) {
int mx = x + d[i][0], my = y + d[i][1];
if (vis[mx][my] == 0 && mp[mx][my] == '#') //注意为什么要判断vis[][]
//继续DFS未搜过的陆地，目的是标记它们
dfs(mx, my);//这个#周围所有的#
}
}
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> mp[i];
int ans = 0 ;
for (int i = 1; i <= n; i++) //DFS所有像素点
for (int j = 1; j <= n; j++)
if (mp[i][j] == '#' && vis[i][j] == 0) {//vis[][]会排除已经搜过的点记忆化的感觉
flag = 0; //假设这个岛被淹
dfs(i, j); //找这个岛中有没有高地，如果有,置flag=1
if (flag == 0) ans++; //这个岛被淹了，统计被淹没岛的数量
}
cout << ans << endl;
return 0;
}
bfs
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char mp[N][N];
int vis[N][N];
int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, { -1, 0}}; //四个方向
int flag;
void bfs(int x, int y) {
queue<pair<int, int>> q;
q.push({x, y});
vis[x][y] = 1; //标记这个'#'被搜过
while (q.size()) {
pair<int, int> t = q.front();
q.pop();
int tx = t.first, ty = t.second;
if ( mp[tx][ty + 1] == '#' && mp[tx][ty - 1] == '#' &&
mp[tx + 1][ty] == '#' && mp[tx - 1][ty] == '#' )
flag = 1; //上下左右都是陆地，不会淹没
for (int i = 0; i < 4; i++) { //扩展(tx,ty)的4个邻居
int nx = tx + d[i][0], ny = ty + d[i][1];
if (vis[nx][ny] == 0 && mp[nx][ny] == '#') { //把陆地放进队列
vis[nx][ny] = 1; //注意：这一句必不可少
q.push({nx, ny});
}
}
}
}
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> mp[i];
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (mp[i][j] == '#' && vis[i][j] == 0) {
flag = 0;
bfs(i, j);
if (flag == 0) ans++; //这个岛全部被淹，统计岛的数量
}
cout << ans << endl;
return 0;
}
岛屿数量问题
dfs
class Solution {
boolean vis[][];//可以原数组经过之后写成0也可以写一个vis
int res=0;
int len1,len2;
int add[][]=new int[][]{{1,0},{-1,0},{0,1},{0,-1}};//别和cpp的声明方法弄混了
public int numIslands(char[][] grid) {
len1=grid.length;
len2=grid[0].length;//注意是长度[0].length
vis=new boolean[len1][len2];//成员变量初始化
for(int i=0;i<len1;++i)
for(int j=0;j<len2;++j){
if(grid[i][j]=='1'&&!vis[i][j]){//vis[]过的'1'不再加
res+=1;
System.out.println(i+" "+j);//test一下
dfs(grid,i,j);//从一个新岛屿开始搜索
}
}
return res;
}
void dfs(char mp[][],int x,int y){
if(uncheck(mp,x,y))return;//在数组之外直接排除
vis[x][y]=true;//没有别排除且已经被搜索vis一下
for(int i=0;i<4;i++){//四个方向搜索一下
int nx=x+add[i][0],ny=y+add[i][1];//新坐标，最好nx ny方便观察，但一定注意后面是不是应该用nx ny不能多用也不能少用
if(!uncheck(mp,nx,ny)&&mp[nx][ny]=='1'&&!vis[nx][ny]){//数组内 是陆地1 没有搜索过
dfs(mp,nx,ny);
}
}
}
boolean uncheck(char mp[][],int x,int y){//判断是否数组内
return x<0||y<0||x>=len1||y>=len2;
}
}
bfs
class Solution {
static boolean vis[][];
static Queue<int[]>q;//Queue 最常见用LinkedList实现
static int add[][]=new int[][]{{1,0},{-1,0},{0,1},{0,-1}};//这种写法一定要注意逗号
static int len1,len2;
public int numIslands(char[][] grid) {
q=new LinkedList<>();
len1=grid.length;
len2=grid[0].length;
int res=0;
vis=new boolean[len1][len2];
for(int i=0;i<len1;i++)
for(int j=0;j<len2;j++){
if(grid[i][j]=='1'&&!vis[i][j]){
q.offer(new int[]{i,j});
vis[i][j]=true;//一进队列直接标注
bfs(grid,i,j);
System.out.println(i+" "+j);
res++;
}
}
return res;
}
void bfs(char mp[][],int x,int y){
while(!q.isEmpty()){
int[]tmp=q.poll();//与cpp不同他会直接蹦出来
x=tmp[0];y=tmp[1];
for(int i=0;i<4;i++){
int nx=x+add[i][0],ny=y+add[i][1];
if(check(mp,nx,ny)&&!vis[nx][ny]&&mp[nx][ny]=='1'){
vis[nx][ny]=true;
q.offer(new int[]{nx,ny});
}
}
}
}
boolean check(char[][] mp,int nx,int ny){
return nx>=0&&ny>=0&&nx<len1&&ny<len2;
}
}
岛屿周长问题
dfs
class Solution {
static int len1,len2;
static boolean vis[][];
static int add[][]=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
int res=0;//这个不能设置成static
public int islandPerimeter(int[][] grid) {
len1=grid.length;
len2=grid[0].length;
vis=new boolean[len1][len2];
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
if(!vis[i][j]&&grid[i][j]==1){
vis[i][j]=true;
dfs(grid,i,j);
}
}
}
return res;
}
void dfs(int mp[][],int x,int y){
for(int i=0;i<4;i++){
int nx=x+add[i][0];int ny=y+add[i][1];
if(!check(nx,ny)){
System.out.println(nx+" "+ny);//测试一下
res++;continue;}//遇到边界周长加一
if(mp[nx][ny]==0){res++;continue;}//遇到0周长加一
if(!vis[nx][ny]){
vis[nx][ny]=true;
dfs(mp,nx,ny);
}
}
}
boolean check(int x,int y){
return x>=0&&y>=0&&x<len1&&y<len2;
}
}
剪枝
bfs判重
蓝桥《跳蚱蜢》八数码问题
012345678—— > 087654321
每层扩展就是蚱蜢跳一次
每次四种跳法（隔 * 2 + 不隔 * 2）判重之后只有9！
#include<bits/stdc++.h>
using namespace std;
struct node {
node() {}
node(string ss, int tt) {s = ss, t = tt;}
string s;
int t;
};
//(1) map
map<string, bool> mp;
//(2) set
// set<string> visited; //记录已经搜索过的状态
queue<node> q;
void solve() {
while (!q.empty()) {
node now = q.front();
q.pop();
string s = now.s;
int step = now.t;
if (s == "087654321") { cout << step << endl; break;} //到目标了，输出跳跃步数
int i;
for (i = 0 ; i < 10 ; i++) //找到盘子的位置i
if (s[i] == '0') break;
for (int j = i - 2 ; j <= i + 2 ; j++) { //4种跳法
int k = (j + 9) % 9;
if (k == i) continue; //这是当前状态，不用检查
string news = s;
char tmp = news[i];
news[i] = news[k];
news[k] = tmp; //跳到一种情况
//(1) map
if (!mp[news]) { //判重：这个情况没有出现过
mp[news] = true;
q.push(node(news, step + 1));
}
//(2)set
/* if(visited.count(news)==0){ //判重：这个情况没有出现过
visited.insert(news);
q.push(node(news, step + 1));
} */
}
}
}
int main() {
string s = "012345678";
q.push(node(s, 0));
//(1) map
mp[s] = true;
solve();
return 0;
}
过会补充Java写法
洪水填充
bfs与最短路
lanqiao的迷宫
#include<bits/stdc++.h>
using namespace std;
struct node {
int x;
int y;
//(1)简单方法：
string path; //path,记录从起点(0,0)到这个点(x,y)的完整路径
};
char mp[31][51]; //存地图
char k[4] = {'D', 'L', 'R', 'U'}; //字典序
int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, { -1, 0}};
int vis[30][50]; //标记。vis=1: 已经搜过，不用再搜
//(2)标准方法：
char pre[31][51]; // 用于查找前驱点。例如pre[x][y] = ‘D’，表示上一个点
//往下走一步到了(x,y)，那么上一个点是(x-1,y)
void print_path(int x, int y) { //打印路径：从(0,0)到(29,49)
if (x == 0 && y == 0) return; //回溯到了起点，递归结束，返回
if (pre[x][y] == 'D') print_path(x - 1, y); //回溯，往上 U
if (pre[x][y] == 'L') print_path(x, y + 1); //回溯，往右 R
if (pre[x][y] == 'R') print_path(x, y - 1);
if (pre[x][y] == 'U') print_path(x + 1, y);
printf("%c", pre[x][y]); //最后打印的是终点
}
void bfs() {
node start; start.x = 0; start.y = 0;
//(1)简单方法：
start.path = "";
vis[0][0] = 1; //标记起点被搜过
queue<node>q;
q.push(start); //把第一个点放进队列，开始BFS
while (!q.empty()) {
node now = q.front(); //取出队首
q.pop();
if (now.x == 29 && now.y == 49) { //第一次达到终点，这就是字典序最小的最短路径
//(1)简单方法：打印完整路径
cout << now.path << endl;
//(2)标准方法：打印完整路径，从终点回溯到起点，打印出来是从起点到终点的正序
print_path(29, 49);
return;
}
for (int i = 0; i < 4; i++) { //扩散邻居结点
node next;
next.x = now.x + dir[i][0]; next.y = now.y + dir[i][1];
if (next.x < 0 || next.x >= 30 || next.y < 0 || next.y >= 50) //越界了
continue;
if (vis[next.x][next.y] == 1 || mp[next.x][next.y] == '1')
continue; //vis=1:已经搜过; mp=1:是障碍
vis[next.x][next.y] = 1; //标记被搜过
//(1)简单方法：记录完整路径：复制上一个点的路径，加上这一步
next.path = now.path + k[i];
//(2)标准方法：记录点(x,y)的前驱
pre[next.x][next.y] = k[i];
q.push(next);
}
}
}
int main() {
for (int i = 0; i < 30; i++) cin >> mp[i]; //读题目给的地图数据
bfs();
return 0;
}
双向广搜
能不能使用
能不能改善复杂度
名虽如此但仍然没有方向感
增长越快优化越明显
看看去重条件之后bfs的劣势还明不明显，不明显可继续使用。相遇和队空为终止条件
1.网格结构
2.树状结构：从下到上和从上到下进行
hdu1195
实现
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
#define MMINF(x) memset(x,INF,sizeof(x))
typedef long long LL;
const double PI=acos(-1.0);
const int N=100010;
struct info
{
char s[5];
int step;
};
info goal,ori;
int pos[N];
int vis[N];
inline int change(char s[])
{
int r=0;
for (int i=0; i<4; ++i)
r=r*10+s[i]-'0';
return r;
}
int T_bfs()
{
queue<info>Qf;
queue<info>Qb;
Qf.push(ori);
Qb.push(goal);
while ((!Qf.empty())||(!Qb.empty()))
{
if(!Qf.empty()&&(Qf.size()>Qb.size()))//这里加了个数量判断就AC了
{
info now1=Qf.front();
Qf.pop();
for (int i=0; i<4; i++)
{
info v=now1;
v.s[i]--;
if(v.s[i]<49)
v.s[i]='9';
int num=change(v.s);
if(!pos[num])
{
v.step=now1.step+1;
pos[num]=1;
vis[num]=v.step;
Qf.push(v);
}
else if(pos[num]==2)
return vis[num]+vis[change(now1.s)];
}
for (int i=0; i<4; i++)
{
info v=now1;
v.s[i]++;
if(v.s[i]>57)
v.s[i]='1';
int num=change(v.s);
if(!pos[num])
{
v.step=now1.step+1;
pos[num]=1;
vis[num]=v.step;
Qf.push(v);
}
else if(pos[num]==2)
return vis[num]+vis[change(now1.s)];
}
for (int i=0; i<3; i++)
{
info v=now1;
swap(v.s[i],v.s[i+1]);
int num=change(v.s);
if(!pos[num])
{
pos[num]=1;
v.step=now1.step+1;
vis[num]=v.step;
Qf.push(v);
}
else if(pos[num]==2)
return vis[num]+vis[change(now1.s)];
}
}
if(!Qb.empty())
{
info now2=Qb.front();
Qb.pop();
for (int i=0; i<4; i++)
{
info v=now2;
v.s[i]--;
if(v.s[i]<49)
v.s[i]='9';
int num=change(v.s);
if(!pos[num])
{
v.step=now2.step+1;
pos[num]=2;
vis[num]=v.step;
Qb.push(v);
}
else if(pos[num]==1)
return vis[num]+vis[change(now2.s)];
}
for (int i=0; i<4; i++)
{
info v=now2;
v.s[i]++;
if(v.s[i]>57)
v.s[i]='1';
int num=change(v.s);
if(!pos[num])
{
v.step=now2.step+1;
pos[num]=2;
vis[num]=v.step;
Qb.push(v);
}
else if(pos[num]==1)
return vis[num]+vis[change(now2.s)];
}
for (int i=0; i<3; i++)
{
info v=now2;
swap(v.s[i],v.s[i+1]);
int num=change(v.s);
if(!pos[num])
{
v.step=now2.step+1;
pos[num]=2;
vis[num]=v.step;
Qb.push(v);
}
else if(pos[num]==1)
return vis[num]+vis[change(now2.s)];
}
}
}
}
int main(void)//不是特别好的方法
{
int tcase;
scanf("%d",&tcase);
while (tcase--)
{
MM(pos);
MM(vis);
scanf("%s %s",ori.s,goal.s);
ori.step=0;
goal.step=0;
pos[change(ori.s)]=1;
pos[change(goal.s)]=2;
vis[change(ori.s)]=0;
vis[change(goal.s)]=0;
!strcmp(ori.s,goal.s)?puts("0"):printf("%d\n",T_bfs()+1);
}
return 0;
}
hdu1401
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
using namespace std;
int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};//四个转移
map<int , int > V,V1; //对应是否有那个状态
struct k{
int x,y;
bool operator < ( const k& b) const{
if ( x == b.x ) return y < b.y;
return x < b.x;
}//排序用的
};
struct stu{
k a[4];
int vis;//记录第几步
}s[2];
int BFS(stu s,int kk){
queue <stu> q;
stu be,nex;
sort(s.a,s.a+4);
int Z = 0;
for (int i = 0; i < 4; i++)
{
Z+= s.a[i].x << (6*i);
Z+= s.a[i].y << (6*i+3);
}//对应每个状态 总共八个点把其从大到小排序后即可化为一个24位的二进制来表示
if(!kk){
V[Z] = 1;
}
else{
V1[Z] = 1;
if(V[Z]) return 1;//二次进入的时候直接判断一下有木有走过即可
}
be = s;
q.push(be);
while(!q.empty())
{
be = q.front(); q.pop();
if( be.vis == 4 ) break;
for (int i = 0; i < 4; i++)//哪个
{
int x = be.a[i].x,y = be.a[i].y;
for (int j = 0; j < 4; j++)//位移
{
int newx = x+dir[j][0],newy = y+dir[j][1];
for (int z = 0; z < 4; z++)
{
if(z != i && newx == be.a[z].x && newy == be.a[z].y)
{
newx += dir[j][0]; newy += dir[j][1];
}
}//再继续翻
if (newx >= 1 && newy <= 8 && newy >= 1 && newy <= 8)
{
nex = be;
nex.a[i].x = newx; nex.a[i].y = newy;
sort(nex.a,nex.a+4); nex.vis = be.vis + 1;
int Z = 0;
for (int i = 0; i < 4; i++) // 转为24位二进制
{
Z+= nex.a[i].x << (6*i);
Z+= nex.a[i].y << (6*i+3);
}
if(!kk)
{
if(! V.count(Z)){
V[Z] = 1;
q.push(nex);
}
}
else
{
if(! V1.count(Z)){
V1[Z] = 1;
if(V[Z]) return 1;
q.push(nex);
}
}//同理
}
}
}
}
return 0;
}
int main()
{
while(~scanf("%d%d",&s[0].a[0].x,&s[0].a[0].y))
{
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 4; j++)
{
if(!i && !j) continue;
scanf("%d%d",&s[i].a[j].x,&s[i].a[j].y);
}
}
V.clear();
V1.clear();
s[0].vis = 0; s[1].vis = 0;//初始化
BFS(s[0],0);
if(BFS(s[1],1)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
p1023
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
const int N = 6;
int n;
string a[N], b[N];
int extend(queue <string>&q, unordered_map <string, int>&da, unordered_map <string, int>&db, string a[], string b[]){
string t = q.front();
q.pop();
for (int i = 0; i < t.size(); i ++)
for (int j = 0; j < n; j ++)
if (t.substr(i, a[j].size()) == a[j]){
string state = t.substr(0, i) +b[j] + t.substr(i + a[j].size());
if(db.count(state)) return da[t] + 1 + db[state];
if(da.count(state)) continue;
da[state] = da[t] + 1;
q.push(state);
}
return 11;
}
int bfs(string A,string B){
queue <string> qa,qb;
unordered_map <string, int> da,db;
qa.push(A), da[A] = 0;
qb.push(B), db[B] = 0;
while(qa.size() && qb.size()){
int t;
if (qa.size() < qb.size()) t = extend(qa, da, db, a, b);
else t = extend(qb, db, da, b, a);
if (t <= 10) return t;
}
return 11;
}
int main(){
string A, B;
cin >> A >> B;
while (cin >> a[n] >> b[n]) n ++;
int step = bfs(A, B);
if (step > 10) puts("NO ANSWER!");
else printf("%d\n", step);
return 0;
}
bfs与优先队列
简单理解为图论上的Dijkstra
优先队列中的元素位置是根据优先级来排的
稀疏图邻接表链式向前星：（n+m）logn
稠密图连接矩阵（边大于点）：n*n不如直接暴力
最短路径dijkstra模板
#include<bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL; //这样定义的好处是: INF <= INF+x
const int N = 3e5+2;
struct edge{
int from, to; //边：起点，终点，权值。起点from并没有用到，e[i]的i就是from
long long w; //边：权值
edge(int a, int b,long long c){from=a; to=b; w=c;}
};
vector<edge>e[N]; //存储图
struct node{
int id; long long n_dis; //id：结点；n_dis：这个结点到起点的距离
node(int b,long long c){id=b; n_dis=c;}
bool operator < (const node & a) const
{ return n_dis > a.n_dis;}
};
int n,m;
int pre[N]; //记录前驱结点
void print_path(int s, int t) { //打印从s到t的最短路
if(s==t){ printf("%d ", s); return; } //打印起点
print_path(s, pre[t]); //先打印前一个点
printf("%d ", t); //后打印当前点。最后打印的是终点t
}
long long dis[N]; //记录所有结点到起点的距离
bool done[N]; //done[i]=true表示到结点i的最短路径已经找到
void dijkstra(){
int s = 1; //起点s = 1
for (int i=1;i<=n;i++) {dis[i]=INF; done[i]=false; } //初始化
dis[s]=0; //起点到自己的距离是0
priority_queue <node> Q; //优先队列，存结点信息
Q.push(node(s, dis[s])); //起点进队列
while (!Q.empty()) {
node u = Q.top(); //pop出距起点s距离最小的结点u
Q.pop();
if(done[u.id]) continue; //丢弃已经找到最短路径的结点。即集合A中的结点
done[u.id]= true;
for (int i=0; i<e[u.id].size(); i++) { //检查结点u的所有邻居
edge y = e[u.id][i]; //u.id的第i个邻居是y.to
if(done[y.to]) continue; //丢弃已经找到最短路径的邻居结点
if (dis[y.to] > y.w + u.n_dis) {
dis[y.to] = y.w + u.n_dis;
Q.push(node(y.to, dis[y.to])); //扩展新邻居，放到优先队列中
pre[y.to]=u.id; //如果有需要，记录路径
}
}
}
// print_path(s,n); //如果有需要，打印路径: 起点1，终点n
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) e[i].clear();
while (m--) {
int u,v,w; scanf("%d%d%lld",&u,&v,&w);
e[u].push_back(edge(u,v,w));
// e[v].push_back(edge(v,u,w)); //本题是单向边
}
dijkstra();
for(int i=1;i<=n;i++){
if(dis[i]>=INF) cout<<"-1 ";
else printf("%lld ", dis[i]);
}
}
图中dijkstra的应用
E.仙人掌墙
每次测试的时间限制2秒
每次测试的内存限制256兆字节
输入标准输入
输出标准输出
Monocarp正在玩Minecraft，他想建造一堵仙人掌墙。他想把它建在一块大小为n×m单元的沙地上。最初，场地的一些单元里有仙人掌。请注意，在Minecraft中，仙人掌不能生长在侧面相邻的单元格上--而初始场地符合这一限制。Monocarp可以种植新的仙人掌（它们也必须满足前述条件）。他不能砍掉任何已经生长在田地上的仙人掌--他没有斧头，而且仙人掌对他的手来说太扎手了。莫诺卡普认为，如果从田地的最上面一排到最下面一排没有路径，那么这堵墙就是完整的，这样。
路径上的每两个连续单元都是相邻的。
属于该路径的单元格中没有仙人掌。
你的任务是种植最小数量的仙人掌来建造一堵墙（或报告说这是不可能的）。输入
第一行包含一个整数t--测试案例的数量。每个测试案例的第一行包含两个整数n和m（2≤n,m≤2⋅1052≤n,m≤2⋅105；n×m≤4⋅105n×m≤4⋅105）--分别为行和列的数量。
然后n行，第i行包含一个长度为m的字符串si，其中si,j为'#'，如果在第i行和第j列的交汇处长有仙人掌。否则，si,jsi,j为'.'。
所有测试案例的n×m之和不超过4⋅1054⋅105。
输出
对于每个测试案例，如果不可能在不违反规则的情况下建造仙人掌墙，则在第一行打印NO。否则，在第一行打印 "是"，然后打印n行，每行有mm个字符--字段本身，其中第ii行的第j个字符等于 "#"，如果在第ii行和第j列的交叉点上有一个仙人掌，否则就是"。如果有多个最佳答案，则打印其中任何一个。
import java.util.Scanner;
import java.util.PriorityQueue;
public class Main{
static final int N = (int)4e5 + 9;
static boolean[][] field;
static boolean[] fixed = new boolean[N];
static int[] pre = new int[N], head = new int[N], dist = new int[N];
static int[][] e = new int[N << 2][3];
static int tot, des;
static final int inf = 0x3f3f3f3f;
public static void main(String[] args){
int i, j, m, n, tt;
int u, v, w;
String str;
Scanner in = new Scanner(System.in);
StringBuilder ans = new StringBuilder();
tt = in.nextInt();
while(tt -- > 0){
n = in.nextInt();
m = in.nextInt();
field = new boolean[n + 9][m + 9];
for(i = n * m; i > 0; -- i) dist[i] = inf;
for(i = 1; i <= n; ++ i){
str = in.next();
for(j = 0; j < m; ++ j)
field[i][j + 1] = str.charAt(j) == '#';
}
for(i = 1, tot = 0; i <= n; ++ i){
for(j = 2; j <= m; ++ j){
if(field[i][j - 1] || field[i][j + 1]) continue;
if(field[i - 1][j] || field[i + 1][j]) continue;
v = (i - 1) * m + j; w = 1;
if(field[i][j]) w = 0;
if(i > 1){
u = (i - 1 - 1) * m + j - 1;
ae(u, v, w);
if(j < m){
u = (i - 1 - 1) * m + j + 1;
ae(u, v, w);
}
}
if(i < n){
u = (i + 1 - 1) * m + j - 1;
ae(u, v, w);
if(j < m){
u = (i + 1 - 1) * m + j + 1;
ae(u, v, w);
}
}
}
}
for(i = v = 1, u = 0; i <= n; ++ i, v += m){
if(field[i][2]) continue;
if(field[i - 1][1]|| field[i + 1][1]) continue;
if(field[i][1]) w = 0;
else w = 1;
ae(u, v, w);
}
dijkstra(0, m);
if(des > 0){
ans.append("YES\n");
while(des > 0){
i = (des + m - 1) / m; j = des % m;
if(j == 0) j = m;
field[i][j] = true; des = pre[des];
}
for(i = 1; i <= n; ++ i){
for(j = 1; j <= m; ++ j)
if(field[i][j]) ans.append('#');
else ans.append('.');
ans.append('\n');
}
}
else ans.append("NO\n");
for(i = n * m; i >= 0; -- i){
head[i] = 0; fixed[i] = false;
}
}
System.out.printf("%s", ans);
}
static void ae(int u, int v, int w){
e[++ tot][0] = v; e[tot][1] = head[u];
e[tot][2] = w; head[u] = tot;
}
static void dijkstra(int s, int m){
int i, u, v, w;
PriorityQueue<node> pq = new PriorityQueue<>();
pq.add(new node(s, 0));
while(!pq.isEmpty()){
u = pq.poll().ind;
if(u > 0 && u % m == 0){
des = u; break;
}
for(i = head[u]; i > 0; i = e[i][1]){
v = e[i][0]; w = e[i][2];
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w; pre[v] = u;
pq.add(new node(v, dist[v]));
}
}
}
}
}
class node implements Comparable<node>{
int ind, dis;
node(int a, int b){
ind = a; dis = b;
}
//public int compare(node o1, node o2) {
// return o2.dis - o1.dis; //大的在前
// }
public int compareTo(node z){
if(dis < z.dis) return -1;
else if(dis > z.dis) return 1;
return 0;
}
}
bfs与双端队列
解决图的边权为1or0的特殊图情况
switch the lamp on
#include<bits/stdc++.h>
using namespace std;
const int dir[4][2] = {{-1,-1},{-1,1},{1,-1},{1,1}}; //4个方向的位移
const int ab[4] = {2,1,1,2}; //4个元件期望的方向
const int cd[4][2] = {{-1,-1},{-1,0},{0,-1},{0,0}}; //4个元件编号的位移
int graph[505][505],dis[505][505]; //dis记录结点到起点s的最短路
struct P{ int x,y,dis; }u;
int read_ch(){
char c;
while((c = getchar())!='/' && c != '\\') ; //字符不是'/'和'\'
return c=='/' ? 1 : 2;
}
int main(){
int n, m; cin >>n >>m;
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) graph[i][j] = read_ch();
deque <P> dq;
dq.push_back((P){1,1,0});
dis[1][1] = 0;
while(!dq.empty()){
u = dq.front(), dq.pop_front(); //front()读队头,pop_front()弹出队头
int nx,ny;
for(int i=0;i<=3;++i) { //4个方向
nx = u.x+dir[i][0]; ny = u.y+dir[i][1];
int d = 0; //边权
d = graph[u.x+cd[i][0]][u.y+cd[i][1]]!=ab[i]; //若方向不相等,则d=1
if(nx && ny && nx<n+2 && ny<m+2 && dis[nx][ny]>dis[u.x][u.y]+d){
// 如果一个结点再次进队，那么距离应该更小。实际上，
//由于再次进队时，距离肯定更大，所以这里的作用是阻止再次入队
dis[nx][ny] = dis[u.x][u.y]+d;
if(d==0) dq.push_front((P){nx, ny, dis[nx][ny]}); //边权=0，插到队头
else dq.push_back ((P){nx, ny, dis[nx][ny]}); //边权=1，插到队尾
if(nx==n+1 && ny==m+1) break; //到终点退出。不退也行，队列空自动退
}
}
}
if(dis[n+1][m+1] != 0x3f3f3f3f) cout << dis[n+1][m+1];
else cout <<"NO SOLUTION"; //可能无解，即s到t不通
return 0;
}
A*
贪心最优和dijkstra
贪心出该点距离到终点的最短距离
dijkstra求出到该点最短的路径
f=g+h
对i的评估=起点到该点的代价+该点到终点的代价
g h应当是同样的计算方法 h应该优于所有实际存在的路径
第k路径最短
// poj 2449代码
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1005, M = 100005;
struct edge{ //记录边
int to, w;
//vector edge[i]:起点是i;它有很多边,其中一个边的to是边的终点,w是边长
edge(int a,int b){ to = a, w = b;} //赋值
};
vector <edge>G[M], G2[M]; //G:原图; G2:反图
struct node { //用于dijkstra。记录点，以及点到起点的路径
int id, dis; //id:点；dis：点id到起点的路径长度
node(int a, int b){ id = a, dis = b;} //赋值
bool operator < (const node &u) const { return dis > u.dis; }
};
int dist[N]; //dist[i]: 从s到点i的最短路长度
bool done[N]; //done[i]=ture: 表示到i的最短路已经找到
void dijkstra(int s) { //标准的dijkstra: 求s到其他所有点的最短路
for(int i =0;i<N;i++) {dist[i]=INF; done[i]=false;} //初始化
dist[s] = 0; //起点s到自己的距离是0
priority_queue<node> q;
q.push(node(s, dist[s])); //从起点开始处理队列
while (!q.empty()) {
node u = q.top(); //pop出距起点s最近的点u
q.pop();
if (done[u.id]) continue; //丢弃已经找到最短路的点
done[u.id] = true; //标记：点u到s的最短路已经找到
for (int i = 0; i< G2[u.id].size(); i++) { //检查点u的所有邻居
edge y = G2[u.id][i];
if (done[y.to]) continue; //丢弃已经找到最短路的邻居
if (dist[y.to] > u.dis + y.w) {
dist[y.to] = u.dis + y.w;
q.push(node(y.to, dist[y.to])); //扩展新的邻居，放进优先队列
}
}
}
}
struct point { //用于 astar
int v, g, h; //评估函数 f = g + h, g是从s到i的长度，h是从i到t的长度
point(int a, int b, int c) { v=a, g=b, h=c; }
bool operator < (const point & b) const { return g + h > b.g + b.h;}
};
int times[N]; //times[i]: 点i被访问的次数
int astar(int s, int t, int k){
memset(times, 0, sizeof(times));
priority_queue<point> q;
q.push(point(s, 0, 0));
while (!q.empty()) {
point p = q.top(); //从优先队列中弹出f = g + h最小的
q.pop();
times[p.v]++;
if (times[p.v] == k && p.v == t) //从队列中第k次弹出t，就是答案
return p.g + p.h;
for (int i = 0; i< G[p.v].size(); i++) {
edge y = G[p.v][i];
q.push(point(y.to, p.g + y.w, dist[y.to]));
}
}
return -1;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
while (m--) {
int a, b, w; //读边：起点、终点、边长
scanf("%d%d%d", &a, &b, &w); //本题是有向图
G[a].push_back(edge(b,w)); //原图
G2[b].push_back(edge(a,w)); //反图
}
int s, t, k;
scanf("%d%d%d", &s, &t, &k);
if (s == t) k++; //一个小陷阱
dijkstra(t); //在反图G2上，求终点t到其他点的最短路
printf("%d\n", astar(s, t, k)); //在原图G上，求第k短路
return 0;
}
IDA* IDDFS
应用
有效基因变换（bfs 双向bfs A* 图论）
基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
- 例如，
"AACCGGTT" --> "AACCGGTA"就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
示例 1：
输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1
BFS
为了方便，我们令 S=start、 T=end，将每个基因序列视为「状态」。
容易想到使用 BFS 进行求解，并使用「哈希表」记录到达某个状态所消耗的步数（同时为了快速判断某个状态是否合法，我们使用 Set 结构对 bank[i] 进行转存）。
起始将 S 加入队列，并更新到达 S 所使用的步数为 0，然后进行常规的 BFS 过程：每次取出队头元素，尝试替换当前状态的某一位，来得到新的状态（限定新状态必须合法，即必须出现在 Set 中），如果新状态合法并且没有在记录步数的哈希表中出现过，则将新状态入队并更新得到新状态所用步数，否则丢弃新状态。
重复上述过程直到找到 T（返回具体步数） 或者队列为空（返回 −1）。
代码：
Java
class Solution {
static Deque<String>d;
static char chs[]=new char[]{'A','C','G','T'};//根据题目规定 你ABCD是什么牛马
static String S,T;
static Map<String,Integer>map=new HashMap<>();//切记切记因为有很多样例所以必须clear
static Set<String>banks=new HashSet<>();//同上
int res=0;//完全不要static
public int minMutation(String start, String end, String[] bank) {
d=new ArrayDeque<>();
S=start;T=end;
for(String s:bank){
banks.add(s);
}
d.addLast(S);
map.put(S,0);
bfs();
map.clear();//clear
banks.clear();//clear
d.clear();//
return res;
}
void bfs(){
while(!d.isEmpty()){
// int size = d.size();// 广度优先搜索， 把这一层所有的元素都取出来进行操作
// while (size-- > 0) {//没有也可以
String tmp=d.pollFirst();
char[] mchs=tmp.toCharArray();
int step=map.get(tmp);
for(int i=0;i<8;i++){
for(char c:chs){
if(mchs[i]==c)continue;
char[]clone=mchs.clone();
clone[i]=c;
String sub=String.valueOf(clone);
if(!banks.contains(sub))continue;
if(map.containsKey(sub))continue;
if(sub.equals(T)){res=step+1;return;}
map.put(sub,step+1);
d.addLast(sub);
}
}
// }
}
res=-1;
return;
}
}
- 时间复杂度：令 n为
bank的数组长度（合法状态数），将bank存入Set结构复杂度为 O(n)，每个状态经过一步操作最多拓展出 C=32 个新基因（共有 8 个位置，每个位置有 4个选择），BFS过程复杂度为 O(C∗n)。整体复杂度为 O(C∗n) - 空间复杂度：O(n)
双向 BFS
同理，我们可以使用「双向 BFS」进行求解。
双向 BFS 与常规 BFS 相比，能够有效解决「搜索空间爆炸」的问题：
对双向 BFS 不熟悉的同学可以看前置