質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

受付中

チェスのナイトが出発地点から目標地点まで移動する時のルートを保存、出力したい。BFS Knight's Tour

kalmia
kalmia

総合スコア13

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

5回答

0評価

0クリップ

279閲覧

投稿2022/06/18 17:32

knight's tourという問題で、queueを利用したBFSで作っています。
基盤となるボードの大きさは8x8で、出発点は(0, 0)、目標地点は(6, 7)です。
問題は
1、最短何ステップで到着するかint型で出力。
2、その際通った道を1、2、3、、、と表示する。(参考写真あり)
このようになっています。これの2番で悩んでいます。

大幅な進行を説明します。
盤は2つあり、訪問したマスをマークする(何回目で訪れたかを数字で保存してある)ものと、出力用のものです。2次元arrayで作られています。(int path 出力用、一つの道のみ表示し、他は0にしたい)(int visited)

Moveは別で宣言されているstructで、x座標とy座表を保存できます。(2, 3)このように。
firは初期地点(0、0)がはいっており、destには目標地点(6、7)が保存されています。
*moveはナイトが動くことのできる8種類の座標移動が入っており、(move[0] = {+2, +1},,,)これを一つずつ足すことによって探索をします。
visitedには訪問済みのvertixのマークおよび何回でそのvertixに行けたのかを保存しています。

**今、下のコードではvisitedを丸ごとpathに移していますが、これを最適な道だけをpathに保存したいです。
**
しかし、ずっと考えているのですがアイデアが浮かびません。
ソースコードを全て載せたいのですが、コピー検査もあるはずなので載せれませんでした。
なにかアイデアをいただきたいです。

int shortdistance(Move fir, Move dest, int path[b_size][b_size], int nrMove, Move *move) { int q_limit= pow(nrMove, b_size); struct Node{ int distance; //何回目で到着したかをカウント Move position; //現在位置を表す変数 }; Queue<Node> q(q_limit); int visited[b_size][b_size] = {0, };  //すべてのvertixを未訪問に設定 visited[0][0] = 1; //初期位置を訪問済みにする Node n; n.distance = 0; //何回動いたかカウントする n.position = fir; //現在いる位置を表す q.enqueue(n); while(!q.isEmpty()){ auto v = q.dequeue(); //初期位置を設定 for(int i = 0; i < 8; i++)}  //ナイトの動き方が8種類ある if(v.position == dest){ //目標地点に到着 > その時のdistanceをreturn、mainで出力(問題1番) for(int i = 0; i < b_size; i++){ for(int j = 0; j < b_size; j++){ path[i][j] = visited[i][j]; } } return v.distance; } auto next_v = v; next_v.distance = v.distance + 1; //次に行くvertixのdistanceを1プラスする next_v.position = v.position + movements[i]; //次に行くvertix設定 if((next_v.position.x > b_size) || (next_v.position.y > b_size)){ //boardの範囲を超えたらcontinue continue; } else if((next_v.position.x < 0) || (next_v.position.y < 0)){ //boardの範囲を超えたらcontinue continue; } if(visited[next_v.position.x][next_v.position.y] != 0){ //既に通ったvertexは何もしない continue; } visited[next_v.position.x][next_v.position.y] = next_v.distance + 1; //何回目でvertixに行けたか8x8の盤に保存 q.enqueue(next_v); //新しいvertixをenqueue } } return 0; }

イメージ説明

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。