走迷宫

给定一个 n×mn×m 的二维整数数组，用来表示一个迷宫，数组中只包含 00 或 11，其中 00 表示可以走的路，11 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1)(1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m)(n,m) 处，至少需要移动多少次。

数据保证 (1,1)(1,1) 处和 (n,m)(n,m) 处的数字为 00，且一定至少存在一条通路。

输入格式

第一行包含两个整数 nn 和 mm。

接下来 nn 行，每行包含 mm 个整数（00 或 11），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤1001≤n,m≤100

输入样例：

输出样例：

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 110;
int arr[N][N];
int dist[N][N];
int n, m;
int res;
typedef pair<int, int> PII;
queue<PII> q;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1}; 

int bfs(int x1, int y1) {
    memset(dist, -1, sizeof(dist));
    q.push({x1, y1});
    dist[x1][y1] = 0;
    while (!q.empty()) {
        PII t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 1 || a > n || b < 1 || b > m) continue;
            if (arr[a][b] != 0) continue;
            if (dist[a][b] == -1) {
                q.push({a, b});
                dist[a][b] = dist[t.x][t.y] + 1;
                if (a == n && b == m) return dist[n][m]; 
            }
        }
    }
    return dist[n][m];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    res = bfs(1, 1);
    cout << res << endl;
    return 0;
}

离开中山路

题目背景

《爱与愁的故事第三弹·shopping》最终章。

题目描述

爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在 x1,y1 处，车站在 x2,y2 处。现在给出一个 n×n(n≤1000) 的地图，0 表示马路，1 表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（每两个相邻坐标间距离为 1）。你能帮他解决吗？

输入格式

第 1 行包含一个数 n。

第 2 行到第 n+1 行：整个地图描述（0 表示马路，1 表示店铺，注意两个数之间没有空格）。

第 n+2 行：四个数 x1,y1,x2,y2。

输出格式

只有 1 行，即最短到达目的地距离。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

对于 20% 数据，满足 1≤n≤100。

对于 100% 数据，满足 1≤n≤1000。

#include<bits/stdc++.h>
using namespace std;
const int N=2000;
typedef pair<int, int>PII;
int x2, y2;
char arr[N][N];
int dist[N][N];
int n;
#define x first
#define y second
int res;
queue<PII> q;
int dx[]={1, 0, -1, 0};
int dy[]={0, -1, 0, 1};
int bfs(int a1, int b1){
	memset(dist, -1, sizeof(dist));
	dist[a1][b1]=0;
	q.push({a1, b1});
	while(!q.empty()){
		PII t=q.front();
		q.pop();
		for(int i=0; i<4; i++){
			int a=t.x+dx[i], b=t.y+dy[i];
			if(a<1 || a>n || b<1 || b>n) continue;
			if(arr[a][b]!='0') continue;
			if(dist[a][b]==-1){
				q.push({a, b});
				dist[a][b]=dist[t.x][t.y]+1;
				if(a==x2 && b==y2) return dist[x2][y2];				
			}
		}
	}
	return dist[x2][y2];
}
int main(){
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
		scanf("%s", arr[i]+1); 
	}
	int x1, y1;
	cin>>x1>>y1>>x2>>y2;
	res=bfs(x1, y1);
	printf("%d", res);
	return 0;
}

马的遍历

题目描述

有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 n,m,x,y。

输出格式

一个 n×m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 −1）。

输入输出样例

输入 #1复制

3 3 1 1

输出 #1复制

0    3    2    
3    -1   1    
2    1    4

#include<bits/stdc++.h>
using namespace std;
const int N=500;
int n, m;
int dist[N][N];
int x, y;
int dx[]={2, 1, -1, -2, -2, -1, 1, 2};
int dy[]={1, 2, 2, 1, -1, -2, -2, -1};
typedef pair<int, int> PII;
queue<PII> q;
void bfs(int x, int y){
	memset(dist, -1, sizeof(dist));
	dist[x][y]=0;
	q.push({x, y});
	while(!q.empty()){
		PII t=q.front();
		q.pop();
		for(int i=0; i<8; i++){
			int a=t.first+dx[i], b=t.second+dy[i];
			if(a<1 || a>n || b<1 || b>m) continue;
			if(dist[a][b]!=-1) continue;
			q.push({a, b}); 
			dist[a][b]=dist[t.first][t.second]+1;
		}
	}
}
int main(){
	scanf("%d%d%d%d", &n, &m, &x, &y);
	bfs(x, y);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			printf("%d ",dist[i][j]);
		}
		printf("\n");
	}
	return 0;
}

血色先锋队

题目背景

巫妖王的天灾军团终于卷土重来，血色十字军组织了一支先锋军前往诺森德大陆对抗天灾军团，以及一切沾有亡灵气息的生物。孤立于联盟和部落的血色先锋军很快就遭到了天灾军团的重重包围，现在他们将主力只好聚集了起来，以抵抗天灾军团的围剿。可怕的是，他们之中有人感染上了亡灵瘟疫，如果不设法阻止瘟疫的扩散，很快就会遭到灭顶之灾。大领主阿比迪斯已经开始调查瘟疫的源头。原来是血色先锋军的内部出现了叛徒，这个叛徒已经投靠了天灾军团，想要将整个血色先锋军全部转化为天灾军团！无需惊讶，你就是那个叛徒。在你的行踪败露之前，要尽快完成巫妖王交给你的任务。

题目描述

军团是一个 n 行 m 列的矩阵，每个单元是一个血色先锋军的成员。感染瘟疫的人，每过一个小时，就会向四周扩散瘟疫，直到所有人全部感染上瘟疫。你已经掌握了感染源的位置，任务是算出血色先锋军的领主们感染瘟疫的时间，并且将它报告给巫妖王，以便对血色先锋军进行一轮有针对性的围剿。

输入格式

第 1 行：四个整数 n，m，a，b，表示军团矩阵有 n 行 m 列。有 a 个感染源，b 为血色敢死队中领主的数量。

接下来 a 行：每行有两个整数 x，y，表示感染源在第 x 行第 y 列。

接下来 b 行：每行有两个整数 x，y，表示领主的位置在第 x 行第 y 列。

输出格式

第 1 至 b 行：每行一个整数，表示这个领主感染瘟疫的时间，输出顺序与输入顺序一致。如果某个人的位置在感染源，那么他感染瘟疫的时间为 0。

输入输出样例

输入 #1复制

输出 #1复制

3
1
3

说明/提示

输入输出样例 1 解释

如下图，标记出了所有人感染瘟疫的时间以及感染源和领主的位置。

数据规模与约定

对于 100% 的数据，保证 1≤n,m≤500，1≤a,b≤105。

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int dist[N][N];
typedef pair<int, int> PII;
int n, m, a, b;
queue<PII> q;
int dx[]={1, 0, -1, 0};
int dy[]={0, -1, 0, 1};
void bfs(){
	while(!q.empty()){
		PII t=q.front();
		q.pop();
		for(int i=0; i<4; i++){
			int a=t.first+dx[i], b=t.second+dy[i];
			if(a<1 || a>n || b<1 || b>m) continue;
			if(dist[a][b]!=-1) continue;
			dist[a][b]=dist[t.first][t.second]+1;
			q.push({a, b});
			
		}
	}
}
int main(){
	memset(dist, -1, sizeof(dist));
	scanf("%d%d%d%d", &n, &m, &a, &b);
	while(a--){
		int x, y;
		scanf("%d%d", &x, &y);
		q.push({x, y});
		dist[x][y]=0;
	}
	bfs(); 
	while(b--){
		int x, y;
		scanf("%d%d",&x, &y);
		printf("%d\n",dist[x][y]);
	}
	return 0;
}

好奇怪的游戏

题目背景

《爱与愁的故事第三弹·shopping》娱乐章。

调调口味来道水题。

题目描述

爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点 x1,y1 和 x2,y2 上。它们得从点 x1,y1 和 x2,y2 走到 (1,1)。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到 (1,1) 的最少步数，你能帮他解决这个问题么？

注意不能走到 x 或 y 坐标 ≤0 的位置。

输入格式

第一行两个整数 x1,y1。

第二行两个整数 x2,y2。

输出格式

第一行一个整数，表示黑马到 (1,1) 的步数。

第二行一个整数，表示白马到 (1,1) 的步数。

输入输出样例

输入 #1复制

12 16
18 10

输出 #1复制

8 
9

说明/提示

数据范围及约定

对于 100% 数据，1≤x1,y1,x2,y2≤20。

#include<bits/stdc++.h>
using namespace std;
const int N=21;
int dist[N][N];
int X1, Y1, X2, Y2;
typedef pair<int, int> PII;
queue<PII> q;
int dx[]={2, 1, -1, -2, -2, -1, 1, 2, 2, -2, -2, 2};
int dy[]={1, 2, 2, 1, -1, -2, -2, -1, 2, -2, -2, 2};
void bfs(){
	while(!q.empty()){
		PII t=q.front();
		q.pop();
		for(int i=0; i<12; i++){
			int a=t.first+dx[i], b=t.second+dy[i];
			if(a<1 || a>20 || b<1 || b>20) continue;
			if(dist[a][b]!=-1) continue;
			q.push({a, b});
			dist[a][b]=dist[t.first][t.second]+1;
		} 
	}
}
int main(){
	scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2);
	memset(dist, -1 ,sizeof(dist));
	dist[1][1]=0;
	q.push({1,1});
	bfs();
	printf("%d\n", dist[X1][Y1]);
	printf("%d\n", dist[X2][Y2]); 
	return 0;
}

填涂颜色

题目描述

由数字 0 组成的方阵中，有一任意形状的由数字 1 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 2。例如：6×6 的方阵（n=6），涂色前和涂色后的方阵如下：

如果从某个 0 出发，只向上下左右 4 个方向移动且仅经过其他 0 的情况下，无法到达方阵的边界，就认为这个 0 在闭合圈内。闭合圈不一定是环形的，可以是任意形状，但保证闭合圈内的 0 是连通的（两两之间可以相互到达）。

0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 2 1
1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数 n(1≤n≤30)。

接下来 n 行，由 0 和 1 组成的 n×n 的方阵。

方阵内只有一个闭合圈，圈内至少有一个 0。

输出格式

已经填好数字 2 的完整方阵。

输入输出样例

输入 #1复制

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

输出 #1复制

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

说明/提示

对于 100% 的数据，1≤n≤30。

#include<bits/stdc++.h>
using namespace std;
const int N=31; 
int n; 
typedef pair<int,int> PII;
queue<PII> q;
int m[N][N];
bool st[N][N];
int dx[]={1, 0, -1, 0};
int dy[]={0, -1, 0, 1}; 
void bfs(int x, int y){
	q.push({0, 0});
	st[0][0]=true; 
	while(!q.empty()){
		PII t=q.front();
		q.pop();
		for(int i=0; i<4; i++){
			int a=t.first+dx[i], b=t.second+dy[i];
			if(a<0 || a>n+1 || b<0 || b>n+1) continue;
			if(st[a][b] || m[a][b]==1) continue;
			st[a][b]=true;
			q.push({a, b}); 
		} 
	} 
} 
int main(){
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			scanf("%d", &m[i][j]);
		}
	}
	bfs(0, 0);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(m[i][j]==0 && !st[i][j]){
				m[i][j]=2;
			}
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			printf("%d ", m[i][j]);
		}
		printf("\n");
	} 
	return 0;
}

Meteor Shower S

题目描述

贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。

如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。

根据预报，一共有 M 颗流星 (1≤M≤50,000) 会坠落在农场上，其中第 i 颗流星会在时刻 T**i（0≤T**i≤1000）砸在坐标为 (X**i,Y**i)(0≤X**i≤300，0≤Y**i≤300) 的格子里。流星的力量会将它所在的格子，以及周围 4 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。

贝茜在时刻 0 开始行动，她只能在会在横纵坐标 X,Y≥0 的区域中，平行于坐标轴行动，每 1 个时刻中，她能移动到相邻的（一般是 4 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 t 被流星撞击或烧焦，那么贝茜只能在 t 之前的时刻在这个格子里出现。贝茜一开始在 (0,0)。

请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 −1。

输入格式

共 M+1 行，第 1 行输入一个整数 M，接下来的 M 行每行输入三个整数分别为 X**i,Y**i,T**i。

输出格式

贝茜到达安全地点所需的最短时间，如果不可能，则为 −1。

[显示翻译](javascript:void 0)

题意翻译

输入输出样例

输入 #1复制

输出 #1复制

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int fire[N][N];
int m;
int dx[]={1, 0, -1, 0};
int dy[]={0, 1, 0 ,-1};
int dist[N][N];
typedef pair<int, int> PII;
queue<PII> q;
int bfs(int x, int y){
	dist[x][y]=0;
	q.push({x, y});
	while(!q.empty()){
		PII t=q.front();
		q.pop();
		for(int i=0; i<4; i++){
			int a=t.first+dx[i], b=t.second+dy[i];
			if(a<0 || b<0) continue;
			if(dist[a][b]!=-1 || dist[t.first][t.second]+1>=fire[a][b]) continue;
			q.push({a, b});
			dist[a][b]=dist[t.first][t.second]+1;
			if(fire[a][b]>=1e8) return dist[a][b];
		}
	}
	return -1;
} 
int main(){
	memset(fire, 0x3f, sizeof(fire));
	memset(dist, -1, sizeof(dist));
	scanf("%d",&m);
	for(int i=0; i<m; i++){
		int x, y, t;
		scanf("%d%d%d", &x, &y, &t);
		fire[x][y]=min(t, fire[x][y]);
		for(int j=0; j<4; j++){
			int a=x+dx[j], b=y+dy[j];
			if(a<0 || a>301 || b<0 || b>301) continue;
			fire[a][b]=min(fire[a][b] ,t);
		}
	}
	if(fire[0][0] > 1e8){
	    printf("-1");
	    return 0;
	}
	int res=bfs(0, 0);
	printf("%d", res);
	return 0;
}

汽车拉力比赛(有个点过不了，不知道为什么)

题目描述

博艾市将要举行一场汽车拉力比赛。

赛场凹凸不平，所以被描述为 N∗M 的网格来表示海拔高度 (1≤M,N≤500)，每个单元格的海拔范围在 0 到 109 之间。

其中一些单元格被定义为路标。组织者希望给整个路线指定一个难度系数 D，这样参赛选手从任一路标到达别的路标所经过的路径上相邻单元格的海拔高度差不会大于 D 。也就是说这个难度系数 D 指的是保证所有路标相互可达的最小值。任一单元格和其东西南北四个方向上的单元格都是相邻的。

输入格式

第 1 行两个整数 M 和 N。第 2 行到第 M+1 行，每行 N 个整数描述海拔高度。第 2+M 行到第 1+2M

行，每行 N 个整数，每个数非 0 即 1，1 表示该单元格是一个路标。

输出格式

一个整数，即赛道的难度系数 D。

输入输出样例

输入 #1复制

3 5 
20 21 18 99 5  
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1

输出 #1复制

#include<bits/stdc++.h>
using namespace std;
const int N=501;
int n, m;
int height[N][N];
int flag[N][N];
int flag_cnt;
int startX, startY;
bool break0;
int dx[]={1, 0, -1, 0};
int dy[]={0, -1, 0, 1};
typedef pair<int, int> PII;
queue<PII> q;
bool st[N][N];
bool check(long long mid){
	memset(st, false, sizeof(st));
	int cnt=1;
	q.push({startX, startY});
	st[startX][startY]=true;
	while(!q.empty()){
		PII t=q.front();
		q.pop();
		for(int i=0; i<4; i++){
			long long a=t.first+dx[i], b=t.second+dy[i];
			if(a<1 || a>n || b<1 || b>m) continue;
			if(st[a][b]) continue;
			if(abs(height[a][b]-height[t.first][t.second])>mid) continue;
			q.push({a, b});
			st[a][b]=true;
			if(flag[a][b]==1){
				cnt++;
			}
			if(cnt==flag_cnt) return true;
		}
	}
    while(!q.empty()){
        q.pop();
    }
	return false;
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%d", &height[i][j]);
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%d", &flag[i][j]);
			if(flag[i][j]==1){
				flag_cnt++;
			}
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(flag[i][j]==1){
				startX=i;
				startY=j;
				break0=true;
				break;
			}
		}
		if(break0){
			break;
		}		
	}
	long long l=0, r=1e9+10;
	while(l+1<r){
		long long mid=l+r>>1;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	if(check(r-1)){
		cout<<r-1<<endl;
	}	
	else{
		cout<<r<<endl;
	}
	return 0;
}

小明的游戏

题目描述

小明最近喜欢玩一个游戏。给定一个 n×m 的棋盘，上面有两种格子 # 和 @。游戏的规则很简单：给定一个起始位置和一个目标位置，小明每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是 0，否则费用是 1。请编程计算从起始位置移动到目标位置的最小花费。

输入格式

输入文件有多组数据。
输入第一行包含两个整数 n，m，分别表示棋盘的行数和列数。
输入接下来的 n 行，每一行有 m 个格子（使用 # 或者 @ 表示）。
输入接下来一行有四个整数 x1,y1,x2,y2，分别为起始位置和目标位置。
当输入 n，m 均为 0 时，表示输入结束。

输出格式

对于每组数据，输出从起始位置到目标位置的最小花费。每一组数据独占一行。

输入输出样例

输入 #1复制

2 2
@#
#@
0 0 1 1
2 2
@@
@#
0 1 1 0
0 0

输出 #1复制

2
0

说明/提示

对于20%的数据满足：1≤n,m≤10。
对于40%的数据满足：1≤n,m≤300。
对于100%的数据满足：1≤n,m≤500。

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int dist[N][N];
int n, m;
char g[N][N];
typedef pair<int, int> PII;
deque<PII> q;
int startX, startY, endX, endY;
int res; 
int dx[]={1, 0, -1, 0};
int dy[]={0, -1, 0, 1};
int bfs(){
	q.push_front({startX, startY});
	dist[startX][startY]=0;
	while(!q.empty()){
		PII t=q.front();
		q.pop_front();
		for(int i=0; i<4; i++){
			int a=t.first+dx[i], b=t.second+dy[i];
			if(a<0 || a>=n || b<0 || b>=m) continue;
			if(dist[a][b] != -1) continue;
			if(g[a][b]==g[t.first][t.second]){
				q.push_front({a, b});
				dist[a][b]=dist[t.first][t.second]; 
			}else{
				q.push_back({a, b});
				dist[a][b]=dist[t.first][t.second]+1;
			}
			if(a==endX && b==endY){
				return dist[a][b];
			}
		}
	}
	return -1; 
}
int main(){
	scanf("%d%d", &n, &m);
	while(n!=0 && m!=0){
		memset(dist, -1, sizeof(dist));
		for(int i=0; i<n; i++){
			scanf("%s", g[i]);
		}
		scanf("%d%d%d%d", &startX, &startY, &endX, &endY);
		res=bfs();
		q.clear();
		printf("%d\n", res);
		scanf("%d%d", &n, &m);
	}
	return 0;
}

八数码难题

题目描述

在 3×3 的棋盘上，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字。棋盘中留有一个空格，空格用 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用 0 表示。

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

输入输出样例

输入 #1复制

283104765

输出 #1复制

说明/提示

样例解释

图中标有 0 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。

#include<bits/stdc++.h>
using namespace std;
unordered_map<string, int> dist;
string endS = "123804765";
queue<string> q;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};

int bfs(string start) {
	q.push(start);
	dist[start] = 0;
	
	while(!q.empty()) {
		string t = q.front();
		q.pop();
		
		if(t == endS) return dist[t];
		
		int d = dist[t];
		int index = t.find('0');
		int x = index / 3, y = index % 3;
		
		for(int i = 0; i < 4; i++) {
			int a = x + dx[i], b = y + dy[i];
			if(a < 0 || a > 2 || b < 0 || b > 2) continue;
			
			int tmp = a * 3 + b;
			swap(t[tmp], t[index]);
			
			if(!dist.count(t)) {
				dist[t] = d + 1;
				q.push(t);
			}
			
			swap(t[tmp], t[index]);
		}
	}
	return -1; // 无解的情况
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	string start;
	cin >> start;
	
	int res = bfs(start);
	cout << res << endl;
	
	return 0;
}

魔板 Magic Squares

题目背景

在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有 8 个大小相同的格子的魔板：

1234

8765

题目描述

我们知道魔板的每一个方格都有一种颜色。这 8 种颜色用前 8 个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列 {1,2,3,4,5,6,7,8} 来表示。这是基本状态。

这里提供三种基本操作，分别用大写字母 A，B，C 来表示（可以通过这些操作改变魔板的状态）：

A：交换上下两行；

B：将最右边的一列插入最左边；

C：魔板中央四格作顺时针旋转。

下面是对基本状态进行操作的示范：

A：

8765

1234

B：

4123

5876

C：

1724

8635

对于每种可能的状态，这三种基本操作都可以使用。

你要编程计算用最少的基本操作完成基本状态到目标状态的转换，输出基本操作序列。

输入格式

只有一行，包括 8 个整数 a1,a2⋯a8(1≤a1,a2⋯a8≤8)，用空格分开，不换行，表示目标状态。

输出格式

第一行包括一个整数，表示最短操作序列的长度。

第二行在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出 60 个字符。

输入输出样例

输入 #1复制

2 6 8 4 5 7 3 1

输出 #1复制

7 
BCABCCB

#include<bits/stdc++.h>
using namespace std;
string end1;
queue<string> q;
unordered_map<string, int> dist;
unordered_map<string, pair<char, string>> pre;
char g[2][4];
void set1(string state){
	for(int i=0; i<4; i++){
		g[0][i]=state[i];
	}
	for(int i=3, j=4; i>=0; i--, j++){
		g[1][i]=state[j];
	}
}
string get1(){
	string res;
	for(int i=0; i<4; i++){
		res+=g[0][i];
	}
	for(int i=3; i>=0; i--){
		res+=g[1][i];
	}
	return res;
}

string move0(string state){
	set1(state);
	for(int i=0; i<4; i++){
		swap(g[0][i], g[1][i]);
	}
	return get1();
}
string move1(string state){
	set1(state);
	char v0=g[0][3], v1=g[1][3];
	for(int i=3; i>0; i--){
		for(int j=0; j<2; j++){
			g[j][i]=g[j][i-1];
		}
	}
	g[0][0]=v0, g[1][0]=v1;
	return get1();
}
string move2(string state){
	set1(state);
	char tmp=g[0][1];
	g[0][1]=g[1][1];
	g[1][1]=g[1][2];
	g[1][2]=g[0][2];
	g[0][2]=tmp;
	return get1();
}
int bfs(string start, string end1){
	q.push(start);
	dist[start]=0;
	while(!q.empty()){
		string t=q.front();
		q.pop();
		
		if(t==end1){
			return dist[end1];
		}
		
		string m[3];
		m[0]=move0(t);
		m[1]=move1(t);
		m[2]=move2(t);
		
		for(int i=0; i<3; i++){
			string s=m[i];
			if(!dist.count(s)){
				dist[s]=dist[t]+1;
				pre[s] = {char(i + 'A'), t};
				if(s==end1){
					return dist[end1];
				}
				q.push(s);
			}
		}
	}
	
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int x;
	string start;
	for(int i=1; i<=8; i++){
		cin>>x;
		end1+=char(x+'0');
	}
	for(int i=1; i<=8; i++){
		start+=char(i+'0');
	}
	int res=bfs(start, end1);
	
	string res2;
	while(end1!=start){
		res2+=pre[end1].first;
		end1=pre[end1].second;
	}
	reverse(res2.begin(), res2.end());
	cout << res << endl;
	for(int i=0; i<res2.size(); i++){
		cout<<res2[i];
		if((i+1)%60==0) cout<<'\n';
	}
	if(res2.size()%60) cout<<'\n';

	return 0;
}