葡京官网开户网站: 程序人生的博客

本文来源:http://www.613sb.com/qinggan_piaoliang_com/

申博游戏网站直营网,民间投资占固定资产投资的比重也由2000年以前的不足30%,一路攀升至2015年的64%以上。远洋对合伙业务、合伙级别都不设限,你可以把它看成以往背包人制度的延伸。与此同时产生了两个机会:一是同期开始的城镇住房体制改革激活了住房需求;二是邓小平南巡之后的招商引资热以及各地与之相伴随的工业园区建设热潮。网易力图通过善意使用这些资料而为用户提供更好的服务。

(苗菲)万能险不仅是一款寿险产品,也兼具投资型保险的功能,因此,近几年万能险受到多家保险公司重视,其发展也非常迅猛。在对待诸如“外来人口”这类世界难题,除了具有封闭条件的地方,良好的秩序的建立,并不在于强制性实行某种制度,而在于通过细致和到位的服务,把“管理对象”纳入当地社会服务的体系当中。这是一个信号。

交易的标的公司前海国际,财务状况很干净,没有债务和合同风险。相处一段时间后,发现她还有事情瞒着我,在我的强逼下,她又把另一段让我撕心裂肺的经历说了出来,即在她17岁时,跟一个大她12岁的男人恋爱并怀孕,由于她的年龄太小,无法结婚,就把孩子先生下来了。出发点没有错,选择没有错,方向就不会错。“远洋坚守职业经理人底线。

CSDN程序人生公众号官方博客

如何通过编程解决华容道问题?

点击上方“程序人生”,选择“置顶公众号”

第一时间关注程序猿(媛)身边的故事


640?wx_fmt=jpeg


小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。


640?wx_fmt=jpeg

作者

?channingbreeze

已获原作者授权,如需转载,请联系原作者。


今天他就去一家外企面试了。


640?wx_fmt=jpeg


【面试前】


面试前,小史就收到了中英文的面试邀请。


640?wx_fmt=jpeg

去外企面试,最好要能够和面试官英语对话。小史除了复习算法之外,赶紧练起了口语。


640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

【面试现场】


640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

面试官给了小史一个问题。(题目已翻译成中文,请自行脑补英文现场)


题目:我有1到8八个数字,放在一个3x3的九宫格里面,那么会留下一个空格。

640?wx_fmt=jpeg

空格可以和上下左右的数字进行交换,你可以认为空格在移动。如果移动成

640?wx_fmt=jpeg

则游戏胜利。

你需要完成以下2件事情:

1、给出数据结构来描述这个过程。

2、给你一个初始状态,告诉我能不能胜利,并给出如何移动才能胜利。

这有点像咱们中国的华容道游戏。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史把他能想到的都写了下来。


import?java.util.LinkedList;
import?java.util.List;

/**
?*?@author?xiaoshi?on?2018/9/8.
?*/

public?class?HuaRongDao?{

????/?定义方向
????public?static?final?int?LEFT?=?1;
????public?static?final?int?RIGHT?=?2;
????public?static?final?int?UP?=?3;
????public?static?final?int?DOWN?=?4;

????/?3x3的九宫格
????private?int[][]?arr;

????/?记录空格的位置
????private?int?x;
????private?int?y;

????/?定义移动的数组
????private?List<Integer>?moveArr?=?new?LinkedList<Integer>();

????/?初始化,数字0代表空格,先遍历,找出空格的位置
????public?HuaRongDao(int[][]?arr)?{
????????this.arr?=?arr;
????????for(int?i=0;?i<arr.length;?i++)?{
????????????for(int?j=0;?j<arr.length;?j++)?{
????????????????if(arr[i][j]?==?0)?{
????????????????????x?=?i;
????????????????????y?=?j;
????????????????}
????????????}
????????}
????}

????/?判断是否可以朝某个方向进行移动
????public?boolean?canMove(int?direction)?{
????????switch?(direction)?{
????????????/?y?>?0才能左移
????????????case?LEFT:
????????????????return?y?>?0;
????????????/?y?<?2才能右移
????????????case?RIGHT:
????????????????return?y?<?2;
????????????/?x?>?0才能上移
????????????case?UP:
????????????????return?x?>?0;
????????????/?x?<?2才能下移
????????????case?DOWN:
????????????????return?x?<?2;
????????}
????????return?false;
????}

????/?朝某个方向进行移动,该函数不作判断,直接移动
????/?调用前请自行用canMove先行判断
????public?void?move(int?direction)?{
????????int?temp;
????????switch?(direction)?{
????????????/?空格和左侧数字交换
????????????case?LEFT:
????????????????temp?=?arr[x][y?-?1];
????????????????arr[x][y?-?1]?=?0;
????????????????arr[x][y]?=?temp;
????????????????y?=?y?-?1;
????????????????break;
????????????/?空格和右侧数字交换
????????????case?RIGHT:
????????????????temp?=?arr[x][y?+?1];
????????????????arr[x][y?+?1]?=?0;
????????????????arr[x][y]?=?temp;
????????????????y?=?y?+?1;
????????????????break;
????????????/?空格和上方数字交换
????????????case?UP:
????????????????temp?=?arr[x?-?1][y];
????????????????arr[x?-?1][y]?=?0;
????????????????arr[x][y]?=?temp;
????????????????x?=?x?-?1;
????????????????break;
????????????/?空格和下方数字交换
????????????case?DOWN:
????????????????temp?=?arr[x?+?1][y];
????????????????arr[x?+?1][y]?=?0;
????????????????arr[x][y]?=?temp;
????????????????x?=?x?+?1;
????????????????break;
????????}
????}

????/?打印当前华容道的状态
????public?void?print()?{
????????for(int?i=0;?i<arr.length;?i++)?{
????????????for(int?j=0;?j<arr.length;?j++)?{
????????????????System.out.print(arr[i][j]);
????????????????System.out.print("?");
????????????}
????????????System.out.println();
????????}
????}

}

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

【请教大神】


小史回到学校,把面试的情况和计算机学院的吕老师说了一下。


640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg


【迷宫问题】


640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:每个点都可以按照右下左上的方向来进行尝试,如果是墙壁,就换一个方向,如果可以走,就往前走到下一点,然后再接着尝试。直到到达终点为止。


640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

吕老师随手又画了一个迷宫。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

吕老师:小史,这块并不是往左走,而是回退,退回到上一步。如果我们正在往前搜索,当然不能走回头路。但是当前面没有路的时候,我们就需要返回来,找到之前有可能出现岔路口的地方,再去下一个方向进行搜索。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg


【华容道问题】


640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:吕老师,我明白了,空格在华容道中移动,就好像我在迷宫里走动一样,每次到一个新的状态,就有几个方向可以搜索,如果是之前碰到过的状态,那就不搜索。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

【递归实现回溯】


640?wx_fmt=jpeg

小史:“回溯”的过程有点像栈的操作。往前走一步就像是入栈,到了死胡同,要往回退,就像是出栈。

640?wx_fmt=jpeg

吕老师:这个过程确实是栈的过程,但是直接用栈的话,对于你刚刚接触搜索算法,可能编码比较难。其实你可以用递归来实现这个搜索过程。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:我在走迷宫的时候,每走一步,就把这一步是往哪走的记录下来,但是碰到了死胡同,往回退的时候,我又把之前记录的步骤最后一步去掉。这样一来,达到终点的时候,我记下来的步骤就是一条从起点到终点的路径了。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:记录移动路径,其实就是在真正搜索之前,把方向记录下来,而搜索如果要返回了,则说明该次搜索已经结束,没有结果,应该把该记录去除。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg


【小史的努力】


吃完烤串,喝完小酒,小史和吕老师休闲地走在回学校的路上。


640?wx_fmt=jpeg

640?wx_fmt=jpeg


吕老师笑而不语。


回到宿舍,小史就打开了电脑,手在键盘上飞快地敲了起来。


理解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了:


import?java.util.HashSet;
import?java.util.LinkedList;
import?java.util.List;
import?java.util.Set;

/**
?*?@author?xiaoshi?on?2018/9/8.
?*/

public?class?HuaRongDao?{

????/?定义方向
????private?static?final?int?LEFT?=?1;
????private?static?final?int?RIGHT?=?2;
????private?static?final?int?UP?=?3;
????private?static?final?int?DOWN?=?4;

????/?3x3的九宫格
????private?int[][]?arr;

????/?记录空格的位置
????private?int?x;
????private?int?y;

????/?定义移动的数组
????private?List<Integer>?moveArr?=?new?LinkedList<Integer>();

????/?定义终点状态
????private?static?final?Integer?WIN_STATE?=?123456780;

????/?保存已经搜索过的状态
????private?Set<Integer>?statusSet?=?new?HashSet<Integer>();

????/?初始化,数字0代表空格,先遍历,找出空格的位置
????public?HuaRongDao(int[][]?arr)?{
????????this.arr?=?arr;
????????for(int?i=0;?i<arr.length;?i++)?{
????????????for(int?j=0;?j<arr.length;?j++)?{
????????????????if(arr[i][j]?==?0)?{
????????????????????x?=?i;
????????????????????y?=?j;
????????????????}
????????????}
????????}
????}

????/?判断是否可以朝某个方向进行移动
????private?boolean?canMove(int?direction)?{
????????switch?(direction)?{
????????????/?y?>?0才能左移
????????????case?LEFT:
????????????????return?y?>?0;
????????????/?y?<?2才能右移
????????????case?RIGHT:
????????????????return?y?<?2;
????????????/?x?>?0才能上移
????????????case?UP:
????????????????return?x?>?0;
????????????/?x?<?2才能下移
????????????case?DOWN:
????????????????return?x?<?2;
????????}
????????return?false;
????}

????/?朝某个方向进行移动,该函数不作判断,直接移动
????/?调用前请自行用canMove先行判断
????private?void?move(int?direction)?{
????????int?temp;
????????switch?(direction)?{
????????????/?空格和左侧数字交换
????????????case?LEFT:
????????????????temp?=?arr[x][y?-?1];
????????????????arr[x][y?-?1]?=?0;
????????????????arr[x][y]?=?temp;
????????????????y?=?y?-?1;
????????????????break;
????????????/?空格和右侧数字交换
????????????case?RIGHT:
????????????????temp?=?arr[x][y?+?1];
????????????????arr[x][y?+?1]?=?0;
????????????????arr[x][y]?=?temp;
????????????????y?=?y?+?1;
????????????????break;
????????????/?空格和上方数字交换
????????????case?UP:
????????????????temp?=?arr[x?-?1][y];
????????????????arr[x?-?1][y]?=?0;
????????????????arr[x][y]?=?temp;
????????????????x?=?x?-?1;
????????????????break;
????????????/?空格和下方数字交换
????????????case?DOWN:
????????????????temp?=?arr[x?+?1][y];
????????????????arr[x?+?1][y]?=?0;
????????????????arr[x][y]?=?temp;
????????????????x?=?x?+?1;
????????????????break;
????????}
????????/?该方向记录
????????moveArr.add(direction);
????}

????/?某个方向的回退,该函数不作判断,直接移动
????/?其操作和move方法正好相反
????private?void?moveBack(int?direction)?{
????????int?temp;
????????switch?(direction)?{
????????????/?空格和左侧数字交换
????????????case?LEFT:
????????????????temp?=?arr[x][y?+?1];
????????????????arr[x][y?+?1]?=?0;
????????????????arr[x][y]?=?temp;
????????????????y?=?y?+?1;
????????????????break;
????????????/?空格和右侧数字交换
????????????case?RIGHT:
????????????????temp?=?arr[x][y?-?1];
????????????????arr[x][y?-?1]?=?0;
????????????????arr[x][y]?=?temp;
????????????????y?=?y?-?1;
????????????????break;
????????????/?空格和上方数字交换
????????????case?UP:
????????????????temp?=?arr[x?+?1][y];
????????????????arr[x?+?1][y]?=?0;
????????????????arr[x][y]?=?temp;
????????????????x?=?x?+?1;
????????????????break;
????????????/?空格和下方数字交换
????????????case?DOWN:
????????????????temp?=?arr[x?-?1][y];
????????????????arr[x?-?1][y]?=?0;
????????????????arr[x][y]?=?temp;
????????????????x?=?x?-?1;
????????????????break;
????????}
????????/?记录的移动步骤出栈
????????moveArr.remove(moveArr.size()?-?1);
????}

????/?获取状态,这里把9个数字按顺序组成一个整数来代表状态
????/?方法不唯一,只要能区分九宫格状态就行
????private?Integer?getStatus()?{
????????int?status?=?0;
????????for(int?i=0;?i<arr.length;?i++)?{
????????????for(int?j=0;?j<arr.length;?j++)?{
????????????????status?=?status?*?10?+?arr[i][j];
????????????}
????????}
????????return?status;
????}

????/?搜索方法
????private?boolean?search(int?direction)?{
????????/?如果能够朝该方向行走
????????if(canMove(direction))?{
????????????/?往该方向移动
????????????move(direction);
????????????/?移动后的状态
????????????Integer?status?=?getStatus();
????????????/?如果已经是胜利状态,返回true
????????????if(WIN_STATE.equals(status))?{
????????????????return?true;
????????????}
????????????/?如果是之前走过的状态了,返回false
????????????if(statusSet.contains(status))?{
????????????????/?这一步走错了,回退
????????????????moveBack(direction);
????????????????return?false;
????????????}
????????????/?将当前状态存入set
????????????statusSet.add(status);
????????????/?继续朝四个方向进行搜索
????????????boolean?searchFourOk?=?search(RIGHT)?||?search(DOWN)?||?search(LEFT)?||?search(UP);
????????????if(searchFourOk)?{
????????????????return?true;
????????????}?else?{
????????????????/?这一步走错了,把它的记录去除
????????????????moveBack(direction);
????????????????return?false;
????????????}
????????}
????????return?false;
????}

????/?解题入口方法
????public?boolean?solve()?{
????????Integer?status?=?getStatus();
????????/?如果已经是胜利状态,返回true
????????if(WIN_STATE.equals(status))?{
????????????return?true;
????????}
????????/?初始状态先记录
????????statusSet.add(status);
????????/?朝4个方向进行搜索
????????return?search(RIGHT)?||?search(DOWN)?||?search(LEFT)?||?search(UP);
????}

????/?打印路径
????public?void?printRoute()?{
????????for(int?i=0;?i<moveArr.size();?i++)?{
????????????System.out.print(getDirString(moveArr.get(i)));
????????????System.out.print("?");
????????}
????}

????/?方向与其对应的字符串
????private?String?getDirString(int?dir)?{
????????switch?(dir)?{
????????????case?LEFT:
????????????????return?"左";
????????????case?RIGHT:
????????????????return?"右";
????????????case?UP:
????????????????return?"上";
????????????case?DOWN:
????????????????return?"下";
????????}
????????return?null;
????}

????/?打印当前华容道的状态
????public?void?print()?{
????????for(int?i=0;?i<arr.length;?i++)?{
????????????for(int?j=0;?j<arr.length;?j++)?{
????????????????System.out.print(arr[i][j]);
????????????????System.out.print("?");
????????????}
????????????System.out.println();
????????}
????}

}


几个测试用例下来,小史眉头一皱,发现事情并不简单。

640?wx_fmt=jpeg

小史经过缜密的分析,找到了原因。

640?wx_fmt=jpeg

我可以判断一下,如果某条路走的步数超过100步,就不再走了,赶紧回退。

小史在search函数中增加了moveArr.size()<100的判断,得到了最终结果。

640?wx_fmt=jpeg


【深搜和广搜】


第二天,小史得意洋洋地拿着自己的代码去找吕老师秀起来。


640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:现在的算法,没办法保证得到的解法就是最优解,并且它很容易进入复杂的死胡同出不来,有点像一个死钻牛角尖的人。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

吕老师:深度优先搜索,会在一个方向一直搜下去,直到这条路走不通,才会考虑第二个方向。

640?wx_fmt=jpeg

吕老师:广度优先搜索,是先搜索每一个可行方向的第一步,然后再接着搜索每一个可行方向的第二步。以此类推。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:这个算法似乎没有“回溯”的必要了,没办法再用递归了吧?而且分头搜索这个方式应该怎么实现呢?

640?wx_fmt=jpeg

吕老师:你可以将要搜索的初始状态加到一个队列里,然后每次从队列中取出一个状态,往可以前进的方向前进一步,然后再将该状态放到队列。利用队列先进先出的特点,就可以实现广搜的效果。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:每一步都记录上一步的状态和这次的方向。这样在达到最终胜利状态的时候,可以找到这个状态的上一步。而上一步又可以找到上上步,这不就是链表么?

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg


理解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了:


import?java.util.HashSet;
import?java.util.LinkedList;
import?java.util.List;
import?java.util.Set;

/**
?*?@author?xiaoshi?on?2018/9/9.
?*/

public?class?HuaRongDao?{

????/?定义方向
????private?static?final?int?LEFT?=?0;
????private?static?final?int?RIGHT?=?1;
????private?static?final?int?UP?=?2;
????private?static?final?int?DOWN?=?3;

????/?定义辅助数组
????private?static?final?int[][]?dxdy?=?{{0,?-1},?{0,?1},?{-1,?0},?{1,?0}};

????/?3x3的九宫格
????private?int[][]?arr;

????/?记录空格的位置
????private?int?x;
????private?int?y;

????/?定义移动的数组
????private?List<Integer>?moveArr?=?new?LinkedList<Integer>();

????/?定义终点状态
????private?static?final?Integer?WIN_STATE?=?123456780;

????/?保存已经搜索过的状态
????private?Set<Integer>?statusSet?=?new?HashSet<Integer>();

????/?代表广搜的每一步,通过lastItem链起来
????private?class?SearchItem?{
????????private?Integer?status;
????????private?Integer?dir;
????????private?SearchItem?lastItem;
????????SearchItem(Integer?status,?Integer?dir,?SearchItem?lastItem)?{
????????????this.status?=?status;
????????????this.dir?=?dir;
????????????this.lastItem?=?lastItem;
????????}
????????public?Integer?getStatus()?{return?status;}
????????public?Integer?getDir()?{return?dir;}
????????public?SearchItem?getLastItem()?{return?lastItem;}
????}

????/?广搜的存储队列
????private?List<SearchItem>?statusToSearch?=?new?LinkedList<SearchItem>();

????/?初始化,数字0代表空格,先遍历,找出空格的位置
????public?HuaRongDao(int[][]?arr)?{
????????this.arr?=?arr;
????????getXY();
????}

????/?获取空格的x和y坐标
????private?void?getXY()?{
????????for(int?i=0;?i<arr.length;?i++)?{
????????????for(int?j=0;?j<arr.length;?j++)?{
????????????????if(arr[i][j]?==?0)?{
????????????????????x?=?i;
????????????????????y?=?j;
????????????????}
????????????}
????????}
????}

????/?判断是否可以朝某个方向进行移动
????private?boolean?canMove(int?direction)?{
????????switch?(direction)?{
????????????/?y?>?0才能左移
????????????case?LEFT:
????????????????return?y?>?0;
????????????/?y?<?2才能右移
????????????case?RIGHT:
????????????????return?y?<?2;
????????????/?x?>?0才能上移
????????????case?UP:
????????????????return?x?>?0;
????????????/?x?<?2才能下移
????????????case?DOWN:
????????????????return?x?<?2;
????????}
????????return?false;
????}

????/?找出该方向的相反方向
????private?int?getBackDir(int?direction)?{
????????switch?(direction)?{
????????????/?y?>?0才能左移
????????????case?LEFT:
????????????????return?RIGHT;
????????????/?y?<?2才能右移
????????????case?RIGHT:
????????????????return?LEFT;
????????????/?x?>?0才能上移
????????????case?UP:
????????????????return?DOWN;
????????????/?x?<?2才能下移
????????????case?DOWN:
????????????????return?UP;
????????}
????????return?0;
????}

????/?朝某个方向进行移动,该函数不作判断,直接移动
????/?调用前请自行用canMove先行判断
????private?void?move(int?direction)?{
????????int?temp;
????????temp?=?arr[x?+?dxdy[direction][0]][y?+?dxdy[direction][1]];
????????arr[x?+?dxdy[direction][0]][y?+?dxdy[direction][1]]?=?0;
????????arr[x][y]?=?temp;
????????x?=?x?+?dxdy[direction][0];
????????y?=?y?+?dxdy[direction][1];
????}

????/?某个方向的前进,该函数不作判断,直接移动
????private?void?moveForward(int?direction)?{
????????move(direction);
????????/?该方向记录
????????moveArr.add(direction);
????}

????/?某个方向的回退,该函数不作判断,直接移动
????/?其操作和moveForward方法正好相反
????private?void?moveBack(int?direction)?{
????????move(getBackDir(direction));
????????/?记录的移动步骤出栈
????????moveArr.remove(moveArr.size()?-?1);
????}

????/?获取状态,这里把9个数字按顺序组成一个整数来代表状态
????/?方法不唯一,只要能区分九宫格状态就行
????public?Integer?getStatus()?{
????????int?status?=?0;
????????for(int?i=0;?i<arr.length;?i++)?{
????????????for(int?j=0;?j<arr.length;?j++)?{
????????????????status?=?status?*?10?+?arr[i][j];
????????????}
????????}
????????return?status;
????}

????/?根据状态还原九宫格数组
????/?该方法是getStatus的逆过程
????public?void?recoverStatus(Integer?status)?{
????????for(int?i=0;?i<arr.length;?i++)?{
????????????for(int?j=0;?j<arr.length;?j++)?{
????????????????arr[2?-?i][2?-?j]?=?status?%?10;
????????????????status?=?status?/?10;
????????????}
????????}
????????getXY();
????}

????/?搜索方法
????private?boolean?search()?{
????????/?如果还有要搜索的状态
????????while(statusToSearch.size()?>?0)?{
????????????/?队首出列
????????????SearchItem?item?=?statusToSearch.remove(0);
????????????Integer?status?=?item.getStatus();
????????????/?搜到了
????????????if(status.equals(WIN_STATE))?{
????????????????/?找到路径
????????????????recordRoute(item);
????????????????return?true;
????????????}
????????????/?根据status还原arr和x,y
????????????recoverStatus(status);
????????????/?4个方向进行遍历
????????????for(int?i=0;?i<4;?i++)?{
????????????????/?如果能够朝该方向行走
????????????????if(canMove(i))?{
????????????????????/?向前一步
????????????????????moveForward(i);
????????????????????status?=?getStatus();
????????????????????/?之前搜过的状态
????????????????????if?(statusSet.contains(status))?{
????????????????????????moveBack(i);
????????????????????????/?放弃
????????????????????????continue;
????????????????????}
????????????????????/?新状态加入待搜索
????????????????????statusSet.add(status);
????????????????????statusToSearch.add(new?SearchItem(status,?i,?item));
????????????????????moveBack(i);
????????????????}
????????????}
????????}
????????return?false;
????}

????/?解题入口方法
????public?boolean?solve()?{
????????Integer?status?=?getStatus();
????????/?如果已经是胜利状态,返回true
????????if(WIN_STATE.equals(status))?{
????????????return?true;
????????}
????????/?初始状态先记录
????????statusSet.add(status);
????????/?初始状态进入搜索队列
????????statusToSearch.add(new?SearchItem(status,?null,?null));
????????return?search();
????}

????/?根据链表顺藤摸瓜,找到路径
????private?void?recordRoute(SearchItem?item)?{
????????while(null?!=?item.getLastItem())?{
????????????moveArr.add(0,?item.getDir());
????????????item?=?item.getLastItem();
????????}
????}

????/?打印路径
????public?void?printRoute()?{
????????for(int?i=0;?i<moveArr.size();?i++)?{
????????????System.out.print(getDirString(moveArr.get(i)));
????????????System.out.print("?");
????????}
????}

????/?方向与其对应的字符串
????private?String?getDirString(int?dir)?{
????????switch?(dir)?{
????????????case?LEFT:
????????????????return?"左";
????????????case?RIGHT:
????????????????return?"右";
????????????case?UP:
????????????????return?"上";
????????????case?DOWN:
????????????????return?"下";
????????}
????????return?null;
????}

????/?打印当前华容道的状态
????public?void?print()?{
????????for(int?i=0;?i<arr.length;?i++)?{
????????????for(int?j=0;?j<arr.length;?j++)?{
????????????????System.out.print(arr[i][j]);
????????????????System.out.print("?");
????????????}
????????????System.out.println();
????????}
????}

}


写完代码,小史赶紧运行看下最终结果:


1?2?3?
4?5?6?
8?7?0?
无法胜利
1?2?3?
4?0?6?
7?5?8?
可以胜利,路径为:下?右?
3?4?1?
5?6?0?
8?2?7?
可以胜利,路径为:左?左?上?右?下?左?下?右?右?上?左?左?下?右?上?上?右?下?左?左?上?右?下?右?下?

Process?finished?with?exit?code?0


640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

一个问题一顿饭,吕老师不亏的。


【饭桌上的闲聊】


640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

PS:这次这篇花费了两周时间以及小史两顿饭钱。如果你看到了这里,并且有所收获的话,可以动动手指转发一下哦,小史和吕老师都会感谢你。


- The End -

「若你有原创文章想与大家分享,欢迎投稿。」

加编辑微信ID,备注#投稿#:

程序 丨 druidlost??

小七 丨 duoshangshuang


程序人生地区交流群,了解一下

根据你所在的城市,回复相应关键词“北京”,“沪杭”或“广东”,我会拉你进相应地区群哦~(目前只有该三个地区群)

(注意:进你所在城市或者最希望进的地区群,以上3个地区群不必重复进入,谢谢配合。)


640?wx_fmt=jpeg

上期精彩内容

640?wx_fmt=png

640?wx_fmt=gif

展开阅读全文
申博游戏网站直营网

没有更多推荐了,申博游戏网站直营网

www.678msc.com 申博微信支付充值 www.77msc.com 申博真人游戏登入 菲律宾太阳网址登入 百家乐手机版登入网址
申博娱乐网址 申博安卓手机下载 老虎机支付宝充值 电子游戏支付宝充值 申博太阳城登入 太阳成娱乐成总代理
申博手机下载版 菲律宾申博现金网登入 申博娱乐城直营网 www.22msc.com www.11psb.com www.44sbc.com