文档章节

蓝桥杯 卡片换位

李韬_varyshare
 李韬_varyshare
发布于 2017/03/31 15:14
字数 1135
阅读 322
收藏 0

题目描述:

卡片换位

你玩过华容道的游戏吗?

这是个类似的,但更简单的游戏。

看下面 3 x 2 的格子

+---+---+---+

|  A  |  *   |  *   |

+---+---+---+

|   B  |      |  *  |

+---+---+---+

在其中放5张牌,其中A代表关羽,B代表张飞,* 代表士兵。还有一个格子是空着的。你可以把一张牌移动到相邻的空格中去(对角不算相邻)。游戏的目标是:关羽和张飞交换位置,其它的牌随便在哪里都可以。

输入格式:输入两行6个字符表示当前的局面

输出格式:

一个整数,表示最少多少步,才能把AB换位(其它牌位置随意)

例如,输入:

* A

**B

程序应该输出:

17

再例如,输入:

A B

***

程序应该输出:

12

 思路:

这道题从字面意思是交换a和b,但是根据规则移动的条件只能移动空格周围的卡片。所以基本等价于移动空格,把各种情况遍历一遍找到一种a和b互换的情况。

由于空格只能移动到相邻位置,所以思路也就明确了可以用广度优先搜索。

空格可以移动有四个方位,上下左右。每移动一次就保存移动后的卡片排序,并且移动到该状态需要的步数是移动前的需要的步数加1.

终将有一次会找到一个卡片序列使得a和b相对起始序列是互换的。

简易代码版:


import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class ExchangeAB {
	public static void main(String[] args) {
		String in = "A B***";
		int aOrigin = in.indexOf("A");
		int bOrgin = in.indexOf("B");
		// 保存到某个局面需要的步数
		HashMap<String, Integer> save = new HashMap<>();
		// 广度优先的队列
		Queue<String> queue = new LinkedList<>();
		queue.add(in);
		save.put(in, 0);
		// 移动的方向上下左右
		int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
		// 广度优先固定格式
		while (!queue.isEmpty()) {
			String nowStr = queue.poll();
			int nowStep = save.get(nowStr);
			// 如果A和B已经交换直接输出
			if (nowStr.indexOf("B") == aOrigin && nowStr.indexOf("A") == bOrgin) {
				System.out.println(nowStep);
				return;
			}
			// 定位到空格的位置
			int spacePos = nowStr.indexOf(" ");
			int x = spacePos / 3;
			int y = spacePos % 3;
			char[] nowArr = nowStr.toCharArray();

			// 向周围扩散
			for (int[] arr : move) {
				int tempx = x + arr[0];
				int tempy = y + arr[1];

				if (tempx >= 0 && tempx < 2 && tempy >= 0 && tempy < 3) {
					// 移动空格位置
					exchange(x, y, tempx, tempy, nowArr);
					String tempStr = String.valueOf(nowArr);
					if (save.get(tempStr) == null) {// 如果这个局面没来过则添加到队列
						queue.add(tempStr);
						save.put(tempStr, nowStep + 1);
					}
					// 复原空格位置方便给下个方向移动
					exchange(x, y, tempx, tempy, nowArr);
				}

			}
		}
	}

	public static void exchange(int x1, int y1, int x2, int y2, char[] arr) {
		int pos1 = x1 * 3 + y1;
		int pos2 = x2 * 3 + y2;
		char temp = arr[pos1];
		arr[pos1] = arr[pos2];
		arr[pos2] = temp;
	}
}

详细代码版: 

package real;

import java.awt.Point;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class CardMove {
//有四个移动方位
	public static final int[][] move = { { 1, 0 }, { -1, 0 }, { 0, -1 },
			{ 0, 1 } };

	public static void main(String[] args) {
		String a = "* A**B";//起始顺序(删除换行)
		Queue<String> queue = new LinkedList<String>();
		HashMap<String, Integer> qmap = new HashMap<String, Integer>();
//保存初始状态卡片A和B的位置
		int posia = a.indexOf('A');
		int posib = a.indexOf('B');
		Point preblank = new Point();
		Point blank = new Point();
//广度优先搜索起点是初始的卡片顺序
		queue.add(a);
//保存初始状态顺序,到达该状态需要0步
		qmap.put(a, 0);
		String temp;
//广度优先搜索固定套路^_^一个循环
		while (!queue.isEmpty()) {
//从队列中拿一个卡片序列出来
			a = queue.poll();
			temp = a;
//判断当前卡片顺序是否满足条件(a,b相对于初始顺序互换了)
			if (a.charAt(posib) == 'A' && a.charAt(posia) == 'B') {
				System.out.println(qmap.get(a));
				break;
			}
//找到空格所在位置方便进行移动遍历
			int posiblank = a.indexOf(' ');
//计算出空格坐标
			preblank.x = posiblank / 3;
			preblank.y = posiblank % 3;
//进行移动遍历,空格有四个方向可以走上下左右
			for (int[] arr : move) {
				blank.x = preblank.x + arr[0];
				blank.y = preblank.y + arr[1];
//判断移动后的目标位置是否合法(是不是出了矩阵)
				if (blank.x >= 0 && blank.x <= 1 && blank.y >= 0
						&& blank.y <= 2) {
//把字符串转字符数组,方便进行互换操作
					char[] achar = a.toCharArray();
					int tempindex = blank.x * 3 + blank.y;
//将空格移动到目标位置(就是将目标位置和空格交换)
					char tempchar = achar[tempindex];
					achar[tempindex] = achar[posiblank];
					achar[posiblank] = tempchar;
//判断移动后的卡片序列是不是以前就走过了,走过了就不用再走了
					if (qmap.get(String.valueOf(achar)) != null)
						continue;
//把产生的新的序列保存下来,到的新的序列所需要的步数是老的序列的步数+1
					qmap.put(new String(achar), qmap.get(temp) + 1);
//将新的序列加入到队列中,用于后面的搜索
					queue.add(new String(achar));
				}
			}
		}

	}
}

 

© 著作权归作者所有

李韬_varyshare

李韬_varyshare

粉丝 7
博文 27
码字总数 18588
作品 1
广州
个人站长
私信 提问
蓝桥杯,你怎么看???

蓝桥杯又要报名了,各位大boss们怎么看待蓝桥杯~~~

嘚瑟的小孩
2016/11/29
581
7
【蓝桥杯】2019第十届蓝桥杯B组C++年号字串

小明用字母A 对应数字1,B 对应2,以此类推,用Z 对应26。对于27 以上的数字,小明用两位或更长位的字符串来对应,例如AA 对应27,AB 对 应28,AZ 对应52,LQ 对应329。 请问2019 对应的字符...

Debug客栈
03/27
0
0
请问有没有上学时参加过蓝桥杯的啊。。

学校组织报名蓝桥杯。我报了c++组。想假期时准备准备。但不知到该准备什么?有没有上学时参加过的过来人啊。恳请指点指点。多谢多谢。

solopiggy
2013/01/15
286
2
普通双非计算机大三学生的焦虑

坐标东南沿海福建南部某师范大学(前几年刚什一本),目前大三,有考研打算,没有acm竞赛经历,参加过省级比赛,大学生数学竞赛,景润杯数学竞赛,互联网+创新创业比赛,蓝桥杯,都是打铁。校...

wzpcsdn
2017/11/07
0
0
思想定位,我的下一步

注册oschina也有一年多了,从来没有认真写过一篇博文,在这里总结一下我的2年学习java经历吧。 大二的时候因为不知道自己该做什么,而自己又是计算机专业的学生,因为一个师兄的缘故跟着学习...

我类个擦
2013/09/23
1K
22

没有更多内容

加载失败,请刷新页面

加载更多

一起来学Java8(四)——复合Lambda

在一起来学Java8(二)——Lambda表达式中我们学习了Lambda表达式的基本用法,现在来了解下复合Lambda。 Lambda表达式的的书写离不开函数式接口,复合Lambda的意思是在使用Lambda表达式实现函...

猿敲月下码
25分钟前
8
0
debian10使用putty配置交换机console口

前言:Linux的推广普及,需要配合解决实际应用方能有成效! 最近强迫自己用linux进行实际工作,过程很痛苦,还好通过网络一一解决,感谢各位无私网友博客的帮助! 系统:debian10 桌面:xfc...

W_Lu
57分钟前
10
0
aelf Enterprise 0.8.0 beta有奖公测,“Bug奖金计划”重磅开启

2019年9月30日,aelf Enterprise 0.8.0 beta版正式发布。aelf Enterprise 0.8.0 beta是一个完备的区块链系统, 包含完备的区块链系统、开发套件、开发文档、以及配套的基础应用和基础服务。 ...

AELF开发者社区
58分钟前
10
0
oracle 初始化数据库脚本

create user lpf identified by 123456; create tablespace lpf_ts_cms datafile '/opt/app/oracle/product/11.2.0/lpf.dbf' size 200M; alter user lpf default tablespace lpf_ts_cms; sel......

internetafei
今天
8
0
深入了解Redis底层数据结构

说明 说到Redis的数据结构,我们大概会很快想到Redis的5种常见数据结构:字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set),以及他们的特点和运用场景。不过它们是...

TurboSanil
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部