LiaN

是一只废物捏

0%

【数据结构】BFS & DFS

发表于 更新于 分类于 本文字数： 15k 阅读时长 ≈ 14 分钟
  • 一些BFS

Easy Part

队列queue、O(2^h)、最短路(只有所有边权都是1 的时候才可以用BFS做最短路问题)

1
2
3
4
queue←初始
while queue非空{
	t←队头；扩展队头2
}

AcW-844. 走迷宫

给定地图，求左上走到右下的步数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=105;
int n,m,g[N][N];
int d[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>g[i][j];
			
	memset(d,-1,sizeof d);
	queue<PII>q;
	q.push({1,1});
	d[1][1]=0;
	while(!q.empty()){
		auto temp=q.front();
		int x=temp.first,y=temp.second;
		q.pop();
		for(int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&d[xx][yy]==-1&&g[x][y]==0){
				d[xx][yy]=d[x][y]+1;
				q.push({xx,yy});
			}
		}
	}
	cout<<d[n][m]<<endl;
}

AcWing843 n皇后问题

  • 对于第r行第i列所在的对角线和反对角线

    对角线 dg[r+i]，反对角线udg[n−r+i]中的下标 r+i和 n−r+i 表示的是截距

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int N=30;
char a[N][N];
int n;
bool dg[N],udg[N],col[N];
//dfs(r)在第r行上放皇后 
void dfs(int r){
	if(r==n){
		for(int i=0;i<n;i++) puts(a[i]);//cout<<a[i]<<endl; 
		puts(""); //换行 
		return;
	}
	//针对当前第r行，枚举 
	for(int i=1;i<=n;i++){
		if(!col[i] && !dg[r + i] && !udg[n - r + i]){
			a[r][i]='Q';
			col[i] = dg[r + i] = udg[n - r + i] = true;
			dfs(r+1);
			col[i] = dg[r + i] = udg[n - r + i] = false; 
			a[r][i]='.';
		}	
	}
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++) a[i][j]='.';
	dfs(0);
}

AcWing1101 献给阿尔吉侬的花束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=205;
int n,r,c;
char g[N][N];
int d[N][N];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int bfs(PII st,PII ed){
	queue<PII>q;
	q.push(st);
	d[st.first][st.second]=0;
	while(!q.empty()){
		auto t=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int x=t.first+dx[i],y=t.second+dy[i];
			if(x>=0&&x<r&&y>=0&&y<c&&g[x][y]!='#'&&d[x][y]==-1){
				d[x][y]=d[t.first][t.second]+1;
				PII xy={x,y};
				if(xy==ed) return d[x][y];
				q.push({x,y});
			}
		}
	}
	return -1;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	PII st,ed;
	while(n--){
		memset(d,-1,sizeof d);
		cin>>r>>c;
		for(int i=0;i<r;i++){
			for(int j=0;j<c;j++){
				cin>>g[i][j]; 
				if(g[i][j]=='S') st={i,j};
				if(g[i][j]=='E') ed={i,j};
			}		
		} 
		int ans=bfs(st,ed);
		if(ans!=-1) cout<<ans<<endl;
		else cout<<"oop!"<<endl; 
	}
}

AcWing1113 红与黑

BFS写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=25;
int w,h;
char g[N][N];
int d[N][N];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void bfs(PII st){
	d[st.first][st.second]=1;
	queue<PII> q;
	q.push(st);
	while(!q.empty()){
		auto t=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int x=t.first+dx[i],y=t.second+dy[i];
			if(x>=0&&x<h&&y>=0&&y<w&&d[x][y]==-1&&g[x][y]=='.'){
				d[x][y]=1;
				q.push({x,y});
			}
		}
	}
}
int main(){
	while(1){
		cin>>w>>h;if(w==0&&h==0) break;
		PII st;
		memset(d,-1,sizeof d);
		memset(g,0,sizeof g);
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				cin>>g[i][j];
				if(g[i][j]=='@') st={i,j};
			}
		}
		bfs(st);
		int cnt=0;
		for(int i=0;i<h;i++)
			for(int j=0;j<w;j++){
				if(d[i][j]==1) cnt++;
			}
		cout<<cnt<<endl;
	}
}

DFS写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n,m;
char g[N][N];
int dx[]={0,0,1,-1},dy[]={-1,1,0,0};
int dfs(int x,int y){
	int res=1;
	g[x][y]='#';
	for(int i=0;i<4;i++){
		int a=x+dx[i],b=y+dy[i];
		if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]=='.'){
			res+=dfs(a,b);
		}
	}
	return res;
}
int main(){
	while(cin>>m>>n,n||m){
		for(int i=0;i<n;i++) cin>>g[i];	
		int x,y;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				if(g[i][j]=='@'){
					x=i,y=j;
				}
		cout<<dfs(x,y)<<endl;	
	}
	
}

AcWing1096 地牢大师（三维）

题意

思路

  • 发现有时候代码写不对注意检查：初始点的状态设置是否遗漏，bfs里面坐标的判断有无遗漏，标志数组是否遗漏

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int N=105;
struct Coo{
	int x,y,z;
};//存储xyz坐标 
char g[N][N][N]; //xyz
int d[N][N][N];//存储走到xyz的距离 
int l,r,c;
int dx[]={1,-1,0,0,0,0},dy[]={0,0,1,-1,0,0},dz[]={0,0,0,0,1,-1};
void bfs(Coo st,Coo ed){
	d[st.x][st.y][st.z]=0;
	queue<Coo>q;
	q.push(st);
	while(!q.empty()){
		auto t=q.front();
		q.pop();
		for(int i=0;i<6;i++){
			int x=t.x+dx[i],y=t.y+dy[i],z=t.z+dz[i];
			if(x>=0&&x<r&&y>=0&&y<c&&z>=0&&z<l){//坐标合法 
				if(d[x][y][z]==-1&&g[x][y][z]!='#'){//且没有被走过且可以走 
					d[x][y][z]=d[t.x][t.y][t.z]+1;
					q.push({x,y,z});
				}
			}
		}	
	}
	if(d[ed.x][ed.y][ed.z]!=-1) cout<<"Escaped in "<<d[ed.x][ed.y][ed.z]<<" minute(s)."<<endl;
	else cout<<"Trapped!"<<endl;
}
int main(){
	while(1){
		Coo st,ed;
		memset(d,-1,sizeof d); 
		scanf("%d%d%d",&l,&r,&c);if(l==0) break;
		for(int i=0;i<l;i++)
			for(int j=0;j<r;j++)
				for(int k=0;k<c;k++){
					cin>>g[j][k][i];
					if(g[j][k][i]=='S') st={j,k,i};
					i
                        ed={j,k,i};
				} 
		bfs(st,ed); 
	}
}

Flood Fill算法

  • 针对网格图的题，找连通的块的数目
  • dfs，bfs；dfs有时候可能会有爆栈的风险；都能实现的话用dfs更加方便
  • bfs：

AcWing1233 全球变暖

题意

思路

  • 多少个连通块，遍历
    • 找连通块：遍历BFSorDFS 、或者 并查集
  • 多少个连通块会被淹没掉
    • 如何判断被淹没：一共有多少个单元totoal，多少个单元在边界bound上
    • 等价于==》 total=bound

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1010;
int n;
char g[N][N];
bool st[N][N];//当前点是否被搜索过 
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void bfs(int sx,int sy,int &total,int &bound){
	PII pi={sx,sy};
	queue<PII>q;
	q.push(pi);
	st[sx][sy]=true;//当前第一个点被遍历 记得要标记 
	while(!q.empty()){
		auto t=q.front();
		q.pop();
		total++;
		int is_bound=0;
		//判断当前t是否临海 
		for(int i=0;i<4;i++){
			int x=t.first+dx[i],y=t.second+dy[i];
            //当前t周围的点的坐标合法，且岛屿没有被遍历过
			if(x>=0&&x<n&&y>=0&&y<n&&(!st[x][y])){
				if(g[x][y]=='.') is_bound=1;
				if(g[x][y]=='#'){
					st[x][y]=true; q.push({x,y});
				}
			}
		}
		bound+=is_bound;
	}
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)cin>>g[i];
	int cnt=0;//被淹没的 岛屿的个数
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(!st[i][j]&&g[i][j]=='#'){
				int total=0,bound=0;
				//从当前点开始，统计这个点所在的连通块 
				bfs(i,j,total,bound);
				if(total==bound) cnt++;
			}
		}
	}
	printf("%d",cnt); 
}

AcWing1097 池塘计数

题意

思路

  • dfs：遍历每个W，标记，从当前W开始八个方向深搜；每次从一个W搜完，与之相连的W都变成.
  • bfs：遍历每个W，标记，从当前W开始八个方向宽搜。。。。。

代码

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1010;
int n,m,cnt;
char g[N][N];
int dx[]={0,0,1,-1,1,1,-1,-1};
int dy[]={1,-1,0,0,-1,1,1,-1};
void dfs(int a,int b){
	g[a][b]='.';
	for(int i=0;i<8;i++){
		int x=a+dx[i],y=b+dy[i];
		if(x>=1&&x<=n&&y>=1&&y<=m){
			if(g[x][y]=='W')
				dfs(x,y);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) //cin>>g[i];
	    for(int j=1;j<=m;j++) cin>>g[i][j];
    //连通块问题，从每个点开始bfs or dfs
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(g[i][j]=='W'){
				dfs(i,j);
				cnt++;
			}
				
		}
	cout<<cnt<<endl;
	
}

BFS

标记数组的位置很重要，一定要放在入队（q.push())之前，不然会T掉！
在bfs中，如果对于之后的某个合法位置，应该入队，那么标记数组会有两种方法，第一种是在每次取队首元素的时候，标记已经遍历过当前点了，还有一种方法是在入队之前就马上标记。之前没太注意这个，但是是完全不一样的，对于8个方向，比如向左走一步是合法的，然后不马上标记的话，例如当前向下和向左都是合法的，那么当向下走时候(比如向下先入队了)，那么向左走还会被记录一次，这个很难debug出来，很奇怪的感觉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1010;
int n,m,cnt;
char g[N][N];
int dx[]={0,0,1,-1,1,1,-1,-1};
int dy[]={1,-1,0,0,-1,1,1,-1};
void bfs(int a,int b){
	PII pi={a,b};
	queue<PII>q;
	q.push(pi);
	while(q.size()){
		auto t=q.front();
		//g[t.first][t.second]='.'; 不要在这个位置标记
		q.pop();
		for(int i=0;i<8;i++){
			int x=t.first+dx[i],y=t.second+dy[i];
			if(x>=1&&x<=n&&y>=1&&y<=m){
				if(g[x][y]=='W'){
                    g[x][y]='.';//要在这个位置标记！！！！！！！！！！！
					q.push({x,y});
				}
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>g[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(g[i][j]=='W'){
				bfs(i,j);
				cnt++;
			}	
		}
	cout<<cnt<<endl;
	return 0;	
}

树与图的DFS

  • 有向图存储
    • 邻接矩阵（用的比较少，g[a] [b])，不能存储重边
    • 邻接表：每个节点开了一个表，存着这个点可以走到哪个点（内部点的存储次序无关紧要）

AcW-846. 树的重心

题意

给定一颗树，包含 n个结点（编号 1∼n）和 n−1 条无向边。

找树的重心，并输出将重心删除后，剩余各个连通块中节点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

思路

  • 无向图：建立边的时候两个方向都要建边
  • 枚举删掉每一个点剩余连通块的节点数量的最大值，从各个最大值中找到最小值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=N*2;
int h[N],e[M],ne[M],idx;
int ans=N,n;
bool st[N];//标记是否被遍历 
void init(){
	memset(h,-1,sizeof h);
	idx=0;
}
//插入一条a到b的边：
//在a所对应的邻接表里面插入一个节点b(头插) 
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx,idx++;
}
//从节点u深搜，返回size:以u为根的树中 点的数量 
int dfs(int u){
	st[u]=true;//
	int size=1,res=0;//sum：删掉这个点的连通块大小的最大值 
	for(int i=h[u];i!=-1;i=ne[i]){//遍历u节点的子节点
		int j=e[i];
		if(!st[j]){
			int s=dfs(j);//s：当前子树的大小 
			size+=s;//
			res=max(res,s);
		} 	
	}
	//和删除该点后的父节点的连通块大小 比较 
	res=max(res,n-size);
	ans=min(ans,res); 
	return size;
}
int main(){
	cin>>n;
	init();
	for(int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		add(a,b),add(b,a);
	}
	dfs(1);
	cout<<ans<<endl;
	return 0;
}

树与图的BFS

AcW-847. 图中点的层次 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N];//d[i]存储1号点走到i号点的距离 
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx,idx++;
} 
void bfs(){
	memset(d,-1,sizeof d);//-1标记没走过 
	d[1]=0;//初始化，然后入队 
	queue<int> q;
	q.push(1);
	while(q.size()){
		auto t=q.front();
		q.pop();//扩展 
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];//通过索引i找到t能到的节点编号 
			if(d[j]==-1){
				d[j]=d[t]+1;
				q.push(j);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		add(a,b);
	}
	bfs();
	cout<<d[n]<<endl;
	return 0;
}

AcW-848. 有向图的拓扑序列

题意

给定有向图（可能有重边和自环）

若存在拓扑序列，则输出；不存在则输出-1

若一个由图中所有点构成的序列 A满足：对于图中的每条边 (x,y)，x 在 序列A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。（即：所有的边都是从前指向后的）

有向无环图一定存在拓扑序列：拓扑图

思路

  • 入度=0：没有任何一条边指向它，所以可以排在当前最前面的位置：将其入队
  • 宽搜，枚举所有出边，t→j ，删掉t→j：j的入度-1，
  • 如果j的入度=0，说明j前面的都排好序了，所以j可以入队

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],idx;
queue<int>top;//存放最终序列 
int d[N];//入度 
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx,idx++;
}
bool topsort(){
	queue<int>q;
	//把所有入度为0的点插入队列 
	for(int i=1;i<=n;i++){
		if(!d[i]) q.push(i);
	}
	while(!q.empty()){
		auto t=q.front();
		top.push(t);
		q.pop();
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];//出边的点
			d[j]--; 
			if(d[j]==0) q.push(j);
		} 
	}
	//判断是否所有点都入队
	return top.size()==n;
}
int main(){
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=1;i<=m;i++){
		int a,b;cin>>a>>b;
		add(a,b);
		d[b]++;
	}
	if(topsort()){
		while(!top.empty()){
			cout<<top.front()<<' ';
			top.pop();
		}
	}else cout<<-1<<endl;
	return 0;
}

Medium Part

最小步数模型：状态的转变

区分最短路模型：从一个点到另一个点的最短距离（比如AcW-844走迷宫）

关键：

  1. 状态的存储：
    • queue<状态>
    • unordered_map<状态，步数>dist：记录到达状态的距离
    • unordered_map<状态，<前一个状态,转移操作>：记录前驱，用于路径输出
  2. 状态的切换
    • 根据题意;
    • （下标从0开始）二维到一维：int x = index / row_length, y = index % col_length
  3. 思路：
    • 将初始状态加入到队列，然后BFS扩展，直到找到目标状态为止

AcW-845. 八数码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
1、将每个3x3 理解成一个状态
2、从初始3x3到12345678x最小步数 -> 从初始状态到目标状态 最短路
		类比走迷宫那道题：从左上到右下的最小步数 
3、到达每个状态的对应一个步数：unordered_map<string,int>
4、unordered_map的count()用以统计key在unordered_map中出现的次数。
		实际上，unordered_map不允许有重复的key。
		因此，如果key存在，则count返回1，如果不存在，则count返回0. 
*/
#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int bfs(string start){
	queue<string>q;
	unordered_map<string,int>d;
	
	q.push(start);
	d[start]=0;//unordered_map[key]=value;
	string end="12345678x";
	while(!q.empty()){
		auto t=q.front();
		q.pop();
		if(t==end) return d[t];
		
		int idx=t.find('x');
		int x=idx/3,y=idx%3;
		int dist=d[t];
		for(int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(xx>=0&&xx<3&&yy>=0&&yy<3){
				swap(t[idx],t[xx*3+yy]);
				if(!d.count(t)){
					d[t]=dist+1;
					q.push(t);
				}
				swap(t[idx],t[xx*3+yy]);
			}
		} 	
	}
	return -1;
}
int main(){
	char s[2];
	string start="";
	for(int i=0;i<9;i++){
		cin>>s;
		start+=s[0];
	}
//	cout<<start<<endl;
	cout<<bfs(start)<<endl;
	return 0; 
}
// 2  3  4  1  5  x  7  6  8

AcW-1107. 魔板 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;
char temp[2][4];
//每个状态string，存储上一个状态string 
//经过操作char到达 
unordered_map<string,pair<string,char>>pre;
unordered_map<string,int>d;//存储步数 
void _set(string s){
	for(int i=0;i<4;i++) temp[0][i]=s[i];
	for(int i=0,j=7;i<4,j>3;i++,j--) temp[1][i]=s[j];
}
string get(){
	string res;
	for(int i=0;i<4;i++) res+=temp[0][i];
	for(int i=3;i>=0;i--) res+=temp[1][i];
	return res;
}
//A:交换上下 
string move0(string s){
	_set(s);
 	swap(temp[0],temp[1]);
	return get();
}
//B: 
string move1(string s){
	_set(s);
	char a=temp[0][3],b=temp[1][3];
	for(int i=3;i>=0;i--){
		temp[0][i]=temp[0][i-1];
		temp[1][i]=temp[1][i-1];
	} 
	temp[0][0]=a;
	temp[1][0]=b;	
	return get();
}
//C: 
string move2(string s){
	_set(s);
	char t=temp[0][2];
	temp[0][2]=temp[0][1];
	temp[0][1]=temp[1][1];
	temp[1][1]=temp[1][2];
	temp[1][2]=t;
	return get();
}

int bfs(string start,string end){
	if(start==end) return 0;
	queue<string>q;
	q.push(start);
	d[start]=0;
	
	while(!q.empty()){
		auto t=q.front();
		q.pop();
		string state[3];
		state[0]=move0(t);
		state[1]=move1(t);
		state[2]=move2(t);
		for(int i=0;i<3;i++){
			if(!d.count(state[i])){
				d[state[i]]=d[t]+1;
				pre[state[i]]={t,'A'+i};
				q.push(state[i]); 
				if(state[i]==end){
					return d[state[i]];
				}
			}
		}
	}
	return -1;	
}
int main(){
	string start="12345678";
	string end="";
	for(int i=0;i<8;i++){
		int c;
		cin>>c;
		end+=char(c+'0');
	}
	int ans=bfs(start,end);
	cout<<ans<<endl;
	string res;//从end往前找前驱 
	while(end!=start){
		res+=pre[end].second;
		end=pre[end].first;
	}
	reverse(res.begin(),res.end());
	if(ans>0) cout<<res<<endl;
	return 0;
}