7パズル[1] は8つの正方形[2] のカードとこれらのカードがぴたり[3] と収まる[4] 枠を使って行います。それぞれのカードは互いに区別できるように、0,1,2….7と番号がつけられています。枠には、縦[5] に2個、横に4個のカードを並べることができます。
7パズルを始めるときには、まず枠にすべてのカードを入れます。枠のなかで0のカードだけは、上下左右に隣接する[6] カードと位置を交換することができます。たとえば、枠の状態が図( a )のときに、0のカードの右に隣接した、7のカードと位置を交換すれば、図( b )の状態になります。あるいは、図( a )の状態から0のカードの下に隣接した2のカードと位置を交換すれば図( c )の状態になります。カードの位置を入れ替える操作はこれだけが許されます。図( a )の状態で0のカードと上下左右に隣接するカードは7と2のカードだけなので、これ以外の位置の入れ替えは許されません。
ゲームの目的は、カードをきれいに整列[7] して図( d )の状態にすることです。最初の状態を入力とし、カードをきれいに整列するまでに、必要な最小手数を出力して終了するプログラムを作成してください。ただし、入力されたカードの状態からは図( d )の状態に移ることは可能であるとします。
入力データは、1行に8つの数字が与えられます。これらは、最初の状態のカードの並びを表します。図( a )の数字表現は0,7,3,4,2,5,1,6に、図( c )は2,7,3,4,0,5,1,6となります。
図( a ) 0,7,3,4,2,5,1,6の場合 図( b ) 7,0,3,4,2,5,1,6の場合
図( c ) 2,7,3,4,0,5,1,6の場合 図( d ) 0,1,2,3,4,5,6,7(最終状態)
Input
1つ目のパズルの状態(整数;空白区切り)
2つ目のパズルの状態(整数;空白区切り)
:
:
与えられるパズルの数は1000以下です。
Output
1つ目のパズルの状態から最終状態へ移行する最小手数(整数)
2つ目のパズルの状態から最終状態へ移行する最小手数(整数)
:
:
Sample Input
0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0
Output for the Sample Input
0
1
28
[1]パズル①【ぱずる】
【英】 puzzle
谜,智力测验题。(謎解き。判じもの。)
△数学パズル。/数学游戏。
△クロスワード·パズル。/纵横字谜。
△君にひとつパズルを出そう。/给你出个谜语吧。
[2]正方形③【せいほうけい】
【名】
正方形。(正四角形。)
△正方形に切る。/切成正方形。
[3]ピタリ◎【ぴたり】
【副】
紧密的。恰好。合适。相称。完全一致。(「ぴったり」と言う意味。ちょうど。「ピタ」の誤爆回避。)
△意見がピタリと一致する。/意见恰好一致。
△ピタリドアを閉める。/把门关紧。
△勘定がピタリと合う。/账目准确无误。
[4]収まる③【おさまる】
【自五】
(1)容纳。(入れ物や一定の枠のなかにきちんと入る。)
△ページ内に収まる/归纳在一页纸上。
(2)缴纳。(金品や税が受け取り手に渡される。)
△国庫に収まる/上缴国库。
(3)平息;解决。(解決が付く。片づく。)
△紛争が収まる/纠纷了结。
(4)心满意足。(人が、ふさわしい地位、立場につく。)
△社長に収まる/心满意足的当上社长。
[5]縦①【たて】
【名】
(1)纵,竖(上下の方向。垂直の方向。また,その長さ)。
△縦に書く/竖着写。
△縦に線を引く/竖着划线;画纵〔竖〕线。
△首を縦に振る/点头;同意;赞成。
△縦にならぶ/纵向排列;竖着摆。
△横の物を縦にもしない/懒惰;油瓶倒了都不肯扶起来。
△縦から見ても横から見ても/无论从哪方面看。
(2)长,宽(長い方向)。
△縦10センチ/长〔宽〕十公分。
△その部屋は縦6メートル、横5メートル/这间屋子长六米,宽五米。
[6]接する◎【せっする】
【自动·三类】
(1)接触,相邻,连续,面对。(互いに隔てなくつながる。)
△道路に接する土地。/毗连道路的土地。
△川に接した家。/靠河的房子。
(2)见面,接待。(交わる。応対する。)
△客に接する。/接待客人。
△いいかげんな態度で接する。/马马虎虎地对待。
△愛想よく客に接する。/和颜悦色地接待顾客。
(3)遇到情况。(あう。出くわす。)
△急報に接する。/接到紧急通知。
△いまだ詳報に接していない。/现在还没有收到详细报告。
(4)(数学)相切。(直線もしくは曲線が、他の曲線と一点において接線を共有する。)
△軒を接する。/鳞次栉比。
△ふたつの村は川をはさんで接している。/两个村子隔一条河相连。
[7]整列◎【せいれつ】
【名·自他サ】
(1)排队,排列。(きちんと列をつくって並ぶこと。)
△一列に整列する。/排成一列。
知识共享署名-非商业性使用-相同方式共享:码农场 » AOJ 0121: Seven Puzzle 《挑战程序设计竞赛(第2版)》练习题答案
并不是随便抓一个当作移动对象,比如02134567就还是0,而是0作为空格,是可交换移动的
作者你好,能不能解释下这句dp.find(next) == dp.end()是什么意思 我对STL的东西不怎么懂 谢谢!
dp.find(next) == dp.end()表示不存在 我还是不理解 能详细点吗 不胜感激
我懂了。很巧妙!学习 了!
谢谢作者的代码,我可以问一下
if (dp.find(next) == dp.end())
{
dp[next] = dp[now] + 1;
que.push(next);
}
这一段的意思是不是表示如果他是一个新找到的字符串(说明是最早找到的,所以在map里面是末尾),那我们就入队?
dp.find(next) == dp.end()表示不存在
line.erase(remove(line.begin(), line.end(), ‘ ‘), line.end());这个的有什么用
删空格