网站上有什么作用,自己做网站需要学什么,个人网址怎么填写,想自己做网站 有免费的吗题目描述#xff1a; 在一个 33 的网格中#xff0c;1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 33 的网格中。 例如#xff1a; 1 2 3
x 4 6
7 5 8在游戏过程中#xff0c;可以把 x 与其上、下、左、右四个方向之一的数字交换#xff08;如果存在#xff09;。 我…题目描述 在一个 3×3 的网格中1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。 例如 1 2 3
x 4 6
7 5 8在游戏过程中可以把 x 与其上、下、左、右四个方向之一的数字交换如果存在。 我们的目的是通过交换使得网格变为如下排列称为正确排列 1 2 3
4 5 6
7 8 x例如示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。 交换过程如下 1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x现在给你一个初始网格请你求出得到正确排列至少需要进行多少次交换。 输入格式 输入占一行将 3×3 的初始网格描绘出来。 例如如果初始网格如下所示 1 2 3
x 4 6
7 5 8 则输入为1 2 3 x 4 6 7 5 8 输出格式 输出占一行包含一个整数表示最少交换次数。 如果不存在解决方案则输出 −1。 输入样例
2 3 4 1 5 x 7 6 8输出样例
19 思路 由于此题解法宽搜算法所以我们可以把这样的一种 这样的一种情况看成一个点从这个一点分散下去一个点有很多种情况进行分层 如下图 此图来源于acwing题解中的一位大佬所画由于每个边的权值是1也就是距离所以我们可以利用宽搜天生就带有性质求出最短的路径。 那么这里我们可以看出来这种3*3的矩阵状态很难表示出来 所以我们才用字符串的形式进行存储例如 我们都知道写bfs的时候都是用队列存储所以我们就可以用队列去存储这个字符串 再来思考如何去存储当前状态下的距离呢 我们可以使用C下的unordered_mapstringint,哈希表去存储当前字符串下的距离值是多少然后通过最终我们想要的字符串和变换中的字符串进行比较最后输出距离。 如何判断字符串能变成哪种状态呢 那么就需要用上面我们说的状态转换先把一个字符串转换成3*3的矩阵利用枚举当前x能移动的上下左右四个点就可以做出变换然后再变回字符串。 这里的难点就是一个一维数组如何变成二维数组二维数组如何去变回一维数组 下面一个小技巧希望大家牢记~ 通用公式 一维坐标映射到二维 - (k / n, k % n ) 二维映射一维 - x * n y AC代码
#includeiostream
#includequeue
#includealgorithm
#includeunordered_map
#includecstringusing namespace std;//宽搜求最短路
int bfs(string start)
{//记录要求最终字符串样式string end 12345678x;queuestring q;//队列存储字符串unordered_mapstring,int d;//哈希表存储当前字符串下的对应值(距离)q.push(start);//进队d[start] 0;//第一个距离初始化为0while(q.size()){//取出队首元素auto t q.front();q.pop();//删除//取出当前字符串形式下的距离值int distance d[t];//如果等于我们想要的值那么直接返回距离输出结果if(t end) return distance;//找出x在一维数组下的下标是多少int k t.find(x);//状态转化变成3*3矩阵下的下标int x k / 3, y k % 3;//上下左右偏移量int dx[4] {-1,0,1,0},dy[4] {0,1,0,-1};//枚举x上下左右四个点的偏移量for(int i0;i4;i){//记录信的坐标点3*3矩阵下int a x dx[i],b y dy[i];//判断新坐标是否越界if(a 0 a 3 b 0 b 3){//状态转化变回一维数组下的字符串swap(t[k],t[a*3 b]);//如果哈希表中没有那么就当前距离1if(!d.count(t)){d[t] distance 1;q.push(t);//新字符串进队}//恢复现场变回字符串因为变换一次还有3个位置还没换呢swap(t[k],t[a*3b]);}}}return -1;//找不到就输出-1
}int main()
{string start;for(int i0;i9;i){char c;cin c;start c;}cout bfs(start) endl;return 0;
}
欢迎不会的小伙伴留言~
