找出骑士的所有唯一可能移动。

huangapple
go评论104阅读模式
英文:

Finding all unique possible moves of a knight

问题

我们有一个8x8的棋盘，单元格从1开始编号，我的目标是编写一个带有以下签名的函数：

  1. public static String findPos(int i, int j, int n)

其中参数（i，j）是骑士在棋盘上的起始位置，而n是骑士将要进行的总移动次数（n≥0）。

例如：

调用findPos(1, 1, 0)将返回(1, 1)，因为在0次移动中，骑士只能停留在自己的位置。

调用findPos(1, 1, 1)将返回(1, 1),(2, 3),(3, 2)。

我已经写了一个不太优雅的解决方案，但它会计算骑士在某些情况下可能占据的重复位置，例如调用findPos(1, 1, 2)：

  1. public static String findPos(int i, int j, int n) {
  2.     if (n == 0) {
  3.         if (i >= 1 && j >= 1 && i <= 8 && j <= 8) {
  4.             return "(" + i + ", " + j + ")";
  5.         } else {
  6.             return "";
  7.         }
  8.     } else {
  9.         if (i >= 1 && j >= 1 && i <= 8 && j <= 8) {
  10.             return "(" + i + ", " + j + ")" +
  11.                 findPos(i - 1, j - 2, n - 1) + 
  12.                 findPos(i - 2, j - 1, n - 1) + 
  13.                 findPos(i - 2, j + 1, n - 1) + 
  14.                 findPos(i - 1, j + 2, n - 1) + 
  15.                 findPos(i + 1, j + 2, n - 1) + 
  16.                 findPos(i + 2, j + 1, n - 1) + 
  17.                 findPos(i + 2, j - 1, n - 1) + 
  18.                 findPos(i + 1, j - 2, n - 1);
  19.         } else {
  20.             return findPos(i - 1, j - 2, n - 1) + 
  21.                 findPos(i - 2, j - 1, n - 1) + 
  22.                 findPos(i - 2, j + 1, n - 1) + 
  23.                 findPos(i - 1, j + 2, n - 1) + 
  24.                 findPos(i + 1, j + 2, n - 1) + 
  25.                 findPos(i + 2, j + 1, n - 1) + 
  26.                 findPos(i + 2, j - 1, n - 1) + 
  27.                 findPos(i + 1, j - 2, n - 1);
  28.         }
  29.     }
  30. }

我的问题是：如何改进代码/递归，以便它只返回可能的唯一位置，因为目前它也会返回重复的位置？

英文:

we have a 8x8 board with cells starting from one, my goal is to write such a function with signature :
public static String findPos(int i, int j, int n) which takes parameters (i,j) the starting position of the knight on the board , and n is the total moves it will make(n>=0)

For example:

findPos(1,1,0) will return (1,1) only since with 0 moves the knight can only stay at it's own position

findPos(1,1,1) will return (1,1),(2,3),(3,2)

I have wrote not really pretty solution , however it counts duplicate positions the knight can take in the case for example findPos(1,1,2):

  2. public static String findPos(int i, int j, int n) {
  3. if (n == 0) {
  4. if (i &gt;= 1 &amp;&amp; j &gt;= 1 &amp;&amp; i &lt;= 8 &amp;&amp; j &lt;= 8) {
  5. return &quot;(&quot; + i + &quot;, &quot; + j + &quot; )&quot;;;
  6. } else {
  7. return &quot;&quot;;
  8. }
  9. } else {
  10. if (i &gt;= 1 &amp;&amp; j &gt;= 1 &amp;&amp; i &lt;= 8 &amp;&amp; j &lt;= 8) {
  11. return &quot;(&quot; + i + &quot;, &quot; + j + &quot; )&quot; + findPos(i - 1, j - 2, n - 1)
  12. + findPos(i - 2, j - 1, n - 1)
  13. + findPos(i - 2, j + 1, n - 1)
  14. + findPos(i - 1, j + 2, n - 1)
  15. + findPos(i + 1, j + 2, n - 1)
  16. + findPos(i + 2, j + 1, n - 1)
  17. + findPos(i + 2, j - 1, n - 1)
  18. + findPos(i + 1, j - 2, n - 1);
  19. } else {
  20. return findPos(i - 1, j - 2, n - 1)
  21. + findPos(i - 2, j - 1, n - 1)
  22. + findPos(i - 2, j + 1, n - 1)
  23. + findPos(i - 1, j + 2, n - 1)
  24. + findPos(i + 1, j + 2, n - 1)
  25. + findPos(i + 2, j + 1, n - 1)
  26. + findPos(i + 2, j - 1, n - 1)
  27. + findPos(i + 1, j - 2, n - 1);
  28. }
  29. }
  30. }

My question is :How can I improve the code/recursion so it returns only unique positions it can take, because currently it also writes dublicates?

答案1

得分: 0

在你的代码中，你使用了一个布尔数组来标记访问过的位置，以防止再次调用该位置。

以下是修改后的代码：

  1. static boolean visited[][] = new boolean[9][9];
  2. public static String findPos(int i, int j, int n) {
  3.    if(i<1 || i>8 || j<1 || j>8 || visited[i][j]) return "";
  4.    else {
  5.       visited[i][j] = true;
  6.       if (n == 0) {
  7.          if (i >= 1 && j >= 1 && i <= 8 && j <= 8) {
  8.             return "(" + i + ", " + j + ")";
  9.          } else {
  10.             return "";
  11.          }
  12.       } else {
  13.          if (i >= 1 && j >= 1 && i <= 8 && j <= 8) {
  14.             return "(" + i + ", " + j + ")" + findPos(i - 1, j - 2, n - 1)
  15.                + findPos(i - 2, j - 1, n - 1)
  16.                + findPos(i - 2, j + 1, n - 1)
  17.                + findPos(i - 1, j + 2, n - 1)
  18.                + findPos(i + 1, j + 2, n - 1)
  19.                + findPos(i + 2, j + 1, n - 1)
  20.                + findPos(i + 2, j - 1, n - 1)
  21.                + findPos(i + 1, j - 2, n - 1);
  22.             
  23.          } else {
  24.             
  25.             return findPos(i - 1, j - 2, n - 1)
  26.                + findPos(i - 2, j - 1, n - 1)
  27.                + findPos(i - 2, j + 1, n - 1)
  28.                + findPos(i - 1, j + 2, n - 1)
  29.                + findPos(i + 1, j + 2, n - 1)
  30.                + findPos(i + 2, j + 1, n - 1)
  31.                + findPos(i + 2, j - 1, n - 1)
  32.                + findPos(i + 1, j - 2, n - 1);
  33.          }
  34.       }
  35.    }
  36. }

或者，你可以使用BFS算法来轻松实现这一点。要了解有关BFS算法的更多信息，可以使用这个网站。代码中有详细的说明。（很抱歉使用了C++而不是Java，希望你能理解主要内容）

以下是如何执行这个过程的示例代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. //此数组用于检查位置是否已访问
  4. bool visited[8][8];
  5. //这里创建了一个表示骑士移动方向的数组
  6. int row[] = {-2,-1,+1,+2,+2,+1,-1,-2};
  7. int col[] = {+1,+2,+2,+1,-1,-2,-2,-1};
  8. //根据当前位置和移动编号返回下一个移动
  9. pair<int,int> nextMove(pair<int,int> curPos, int moveNo) {
  10.     return {
  11.         curPos.first+row[moveNo],
  12.         curPos.second+col[moveNo]
  13.     };
  14. }
  15. //检查当前位置是否在棋盘上
  16. bool validity(pair<int,int> curPos) {
  17.     if(curPos.first<1 || curPos.first>8) return false;
  18.     if(curPos.second<1 || curPos.second>8) return false;
  19.     return true;
  20. }
  21. //BFS算法
  22. string bfs(pair<int,int> curPos, int n) {
  23.     //创建表示已访问位置的字符串表示
  24.     string ans = "("+to_string(curPos.first)+","+to_string(curPos.second)+")";
  25.     queue<pair<int,int>> q;
  26.     q.push(curPos);
  27.     //维护级别，以防它超过给定的移动次数“n”
  28.     map<pair<int,int>, int> level;
  29.     level[curPos] = 0;
  30.     visited[curPos.first][curPos.second] = true;
  31.     while(!q.empty()) {
  32.         curPos = q.front();
  33.         if(level[curPos]>=n) break;
  34.         q.pop();
  35.         for(int i=0; i<8; i++) {
  36.             pair<int,int> tempPos = nextMove(curPos,i);
  37.             if(validity(tempPos) && !visited[tempPos.first][tempPos.second]) {
  38.                 level[tempPos] = level[curPos]+1;
  39.                 q.push(tempPos);
  40.                 visited[tempPos.first][tempPos.second] = true;
  41.                 ans += "("+to_string(tempPos.first)+","+to_string(tempPos.second)+")";
  42.             }
  43.         }
  44.     }
  45.     return ans;
  46. }
  47. int main() {
  48.     ios_base::sync_with_stdio(false);
  49.     int i,j,n;
  50.     cin >> i >> j >> n;
  51.     cout << bfs({i,j},n) << "\n";
  52. }

示例输入：

  1. 1 1 2

示例输出：

  1. (1,1)(2,3)(3,2)(1,5)(3,5)(4,4)(4,2)(3,1)(1,3)(2,4)(5,3)(5,1)
英文:

In your code you use a boolean array to keep the visited positions marked and prevent that position from being called again.

Here's the modification:

  1.    static boolean visited[][] = new boolean[9][9];
  2.    public static String findPos(int i, int j, int n) {
  3.       if(i&lt;1 || i&gt;8 || j&lt;1 || j&gt;8 || visited[i][j]) return &quot;&quot;;
  4.       else {
  5.          visited[i][j] = true;
  6.          if (n == 0) {
  7.             if (i &gt;= 1 &amp;&amp; j &gt;= 1 &amp;&amp; i &lt;= 8 &amp;&amp; j &lt;= 8) {
  8.                return &quot;(&quot; + i + &quot;, &quot; + j + &quot; )&quot;;
  9.             } else {
  10.                return &quot;&quot;;
  11.             }
  12.          } else {
  13.             if (i &gt;= 1 &amp;&amp; j &gt;= 1 &amp;&amp; i &lt;= 8 &amp;&amp; j &lt;= 8) {
  14.                return &quot;(&quot; + i + &quot;, &quot; + j + &quot; )&quot; + findPos(i - 1, j - 2, n - 1)
  15.                   + findPos(i - 2, j - 1, n - 1)
  16.                   + findPos(i - 2, j + 1, n - 1)
  17.                   + findPos(i - 1, j + 2, n - 1)
  18.                   + findPos(i + 1, j + 2, n - 1)
  19.                   + findPos(i + 2, j + 1, n - 1)
  20.                   + findPos(i + 2, j - 1, n - 1)
  21.                   + findPos(i + 1, j - 2, n - 1);
  22.                
  23.             } else {
  24.                
  25.                return findPos(i - 1, j - 2, n - 1)
  26.                   + findPos(i - 2, j - 1, n - 1)
  27.                   + findPos(i - 2, j + 1, n - 1)
  28.                   + findPos(i - 1, j + 2, n - 1)
  29.                   + findPos(i + 1, j + 2, n - 1)
  30.                   + findPos(i + 2, j + 1, n - 1)
  31.                   + findPos(i + 2, j - 1, n - 1)
  32.                   + findPos(i + 1, j - 2, n - 1);
  33.             }
  34.          }
  35.       }
  36.    }

Or, you could use the BFS algorithm to achieve this quite easily. To know more about the BFS algorithm, you can use this site. Details are in the code.(Apologies for using C++ instead of Java, I hope you'll be able to get the gist)

Here's how you can do this-

  1. #include&lt;bits/stdc++.h&gt;
  2. using namespace std;
  3. //This array is to check if a position is visited or not
  4. bool visited[8][8];
  5. //Here you&#39;re making a direction array for the move of the knight
  6. int row[] = {-2,-1,+1,+2,+2,+1,-1,-2};
  7. int col[] = {+1,+2,+2,+1,-1,-2,-2,-1};
  8. //Returning the next move based on the current position and the move no
  9. pair&lt;int,int&gt; nextMove(pair&lt;int,int&gt; curPos, int moveNo) {
  10. return {
  11. curPos.first+row[moveNo],
  12. curPos.second+col[moveNo]
  13. };
  14. }
  15. //Checking if the current position is in the board or not
  16. bool validity(pair&lt;int,int&gt; curPos) {
  17. if(curPos.first&lt;1 || curPos.first&gt;8) return false;
  18. if(curPos.second&lt;1 || curPos.second&gt;8) return false;
  19. return true;
  20. }
  21. //BFS algorithm
  22. string bfs(pair&lt;int,int&gt; curPos, int n) {
  23. //Making the string representation of the visited positions
  24. string ans = &quot;(&quot;+to_string(curPos.first)+&quot;,&quot;+to_string(curPos.second)+&quot;)&quot;;
  25. queue&lt;pair&lt;int,int&gt;&gt; q;
  26. q.push(curPos);
  27. //Maintaining level so that it doesn&#39;t exceed the given &quot;n&quot; number of moves
  28. map&lt;pair&lt;int,int&gt;, int&gt; level;
  29. level[curPos] = 0;
  30. visited[curPos.first][curPos.second] = true;
  31. while(!q.empty()) {
  32. curPos = q.front();
  33. if(level[curPos]&gt;=n) break;
  34. q.pop();
  35. for(int i=0; i&lt;8; i++) {
  36. pair&lt;int,int&gt; tempPos = nextMove(curPos,i);
  37. if(validity(tempPos) &amp;&amp; !visited[tempPos.first][tempPos.second]) {
  38. level[tempPos] = level[curPos]+1;
  39. q.push(tempPos);
  40. visited[tempPos.first][tempPos.second] = true;
  41. ans += &quot;(&quot;+to_string(tempPos.first)+&quot;,&quot;+to_string(tempPos.second)+&quot;)&quot;;
  42. }
  43. }
  44. }
  45. return ans;
  46. }
  47. int main() {
  48. ios_base::sync_with_stdio(false);
  49. int i,j,n;
  50. cin &gt;&gt; i &gt;&gt; j &gt;&gt; n;
  51. cout &lt;&lt; bfs({i,j},n) &lt;&lt; &quot;\n&quot;;
  52. }

Sample input:

  1. 1 1 2

Sample output:

  1. (1,1)(2,3)(3,2)(1,5)(3,5)(4,4)(4,2)(3,1)(1,3)(2,4)(5,3)(5,1)

huangapple
  • 本文由 发表于 2020年5月5日 03:02:21
  • 转载请务必保留本文链接：https://go.coder-hub.com/61599673.html
  • algorithm
  • java
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定