騎士游歷問題問題

Problem Statement:

問題陳述：

There is a chessboard of size N×M and starting position (sx, sy) and destination position (dx,dy). You have to find out how many minimum numbers of moves a knight goes to that destination position?

有一個大小為N×M的棋盤，其起始位置(sx，sy)和目標位置(dx，dy) 。 您必須找出一個騎士去那個目的地位置的最小移動次數？

Example:

例：

Input:

輸入：

Check the above example...

檢查上面的例子...

If the source position is (5,5) and the destination position is (3,2).
Then the path count is 3.

如果源位置是(5,5)而目標位置是(3,2) 。
那么路徑計數為3 。

Algorithm:

算法：

To solve this problem we follow this approach:

為了解決這個問題，我們采用以下方法：

1. We use queue data structure and initialize it with the starting position and a map data structure to count the steps where the key is position and value is step count.

   我們使用隊列數據結構，并使用起始位置和地圖數據結構對其進行初始化，以計算步數，其中鍵是位置，值是步數。

2. Then we pop the top position and push all the possible positions that are reached from that position (a knight moves 2 steps at any direction and then one step left or right) and increase the step count of the popped position by one.

   然后，我們彈出頂部位置，并從該位置推動到達所有可能的位置(騎士在任意方向上移動2步，然后向左或向右移動1步)，并將彈出位置的步數增加1。

3. We repeat step 2 until we reach the destination position and the first value is the minimum value.

   重復步驟2，直到到達目標位置，并且第一個值是最小值。

騎士步行問題的C ++實現 (C++ Implementation for Knight walk problem)

#include <bits/stdc++.h>
using namespace std;
int num_x[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int num_y[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
bool isvalid(int r, int c, int row, int col)
{
return (row >= 0 && row < r && col >= 0 && col < c);
}
int count(int r, int c, int sx, int sy, int dx, int dy)
{
queue<pair<pair<int, int>, int> > q;
set<pair<int, int> > st;
q.push(make_pair(make_pair(sx, sy), 0));
while (!q.empty()) {
pair<pair<int, int>, int> p = q.front();
st.insert(make_pair(sx, sy));
if (p.first.first == dx && p.first.second == dy) {
return p.second;
}
q.pop();
for (int i = 0; i < 8; i++) {
int row = p.first.first + num_x[i];
int col = p.first.second + num_y[i];
if (isvalid(r, c, row, col) && st.find(make_pair(row, col)) == st.end()) {
st.insert(make_pair(row, col));
int temp = p.second + 1;
q.push(make_pair(make_pair(row, col), temp));
}
}
}
return -1;
}
int main()
{
int r, c;
cout << "Row: ";
cin >> r;
cout << "Col: ";
cin >> c;
int sx, sy, dx, dy;
cout << "Staring position : ";
cin >> sx >> sy;
cout << "Destination position : ";
cin >> dx >> dy;
cout << "Steps :";
cout << count(r, c, sx - 1, sy - 1, dx - 1, dy - 1) << endl;
return 0;
}

Output

輸出量

Row: 5
Col: 5
Staring position : 5 5
Destination position : 3 2
Steps :3

翻譯自: https://www.includehelp.com/icp/knight-walk-problem.aspx

騎士游歷問題問題