放牧代码和思想
专注自然语言处理、机器学习算法
    This thing called love. Know I would've. Thrown it all away. Wouldn't hesitate.

AOJ 0121: Seven Puzzle 《挑战程序设计竞赛(第2版)》练习题答案

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のカードと上下左右に隣接するカードは72のカードだけなので、これ以外の位置の入れ替えは許されません。

 

ゲームの目的は、カードをきれいに整列[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版)》练习题答案

评论 10

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #4

    并不是随便抓一个当作移动对象,比如02134567就还是0,而是0作为空格,是可交换移动的

    阿不管的啦5年前 (2019-04-21)回复
  2. #3

    作者你好,能不能解释下这句dp.find(next) == dp.end()是什么意思 我对STL的东西不怎么懂 谢谢!

    gdutzhuhui8年前 (2016-03-31)回复
    • dp.find(next) == dp.end()表示不存在 我还是不理解 能详细点吗 不胜感激

      gdutzhuhui8年前 (2016-03-31)回复
      • 我懂了。很巧妙!学习 了!

        gdutzhuhui8年前 (2016-03-31)回复
  3. #2

    谢谢作者的代码,我可以问一下
    if (dp.find(next) == dp.end())
    {
    dp[next] = dp[now] + 1;
    que.push(next);
    }
    这一段的意思是不是表示如果他是一个新找到的字符串(说明是最早找到的,所以在map里面是末尾),那我们就入队?

    Philip9年前 (2015-09-26)回复
    • dp.find(next) == dp.end()表示不存在

      hankcs9年前 (2015-09-26)回复
  4. #1

    line.erase(remove(line.begin(), line.end(), ‘ ‘), line.end());这个的有什么用

    奥特曼9年前 (2015-02-22)回复

我的作品

HanLP自然语言处理包《自然语言处理入门》