POJ 1657-Distance on Chessboard(BFS-多种方向不限步数)

痛定思痛。 2022-06-16 00:56 179阅读 0赞

Distance on Chessboard














Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 26931   Accepted: 9124

Description

国际象棋的棋盘是黑白相间的8 * 8的方格,棋子放在格子中间。如下图所示:
1657_1.jpg
王、后、车、象的走子规则如下:

  • 王:横、直、斜都可以走,但每步限走一格。

  • 后:横、直、斜都可以走,每步格数不受限制。

  • 车:横、竖均可以走,不能斜走,格数不限。

  • 象:只能斜走,格数不限。

写一个程序,给定起始位置和目标位置,计算王、后、车、象从起始位置走到目标位置所需的最少步数。

Input

第一行是测试数据的组数t(0 <= t <= 20)。以下每行是一组测试数据,每组包括棋盘上的两个位置,第一个是起始位置,第二个是目标位置。位置用”字母-数字”的形式表示,字母从”a”到”h”,数字从”1”到”8”。

Output

对输入的每组测试数据,输出王、后、车、象所需的最少步数。如果无法到达,就输出”Inf”.

Sample Input

  1. 2
  2. a1 c3
  3. f5 f8

Sample Output

  1. 2 1 2 1
  2. 3 1 1 Inf

Source

POJ Monthly—2004.05.15 Liu Rujia@POJ

解题思路:

其实吧,这个题阿,不用搜索,数学方法计算距离可过。

然后呢,我想乱搞一下试试手,就全都用BFS了。三c⌒っ゚Д゚)っ

就分情况分别处理四种棋子,记录步数,找到就输出。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <queue>
  5. #include <cmath>
  6. #include <iomanip>
  7. #include <algorithm>
  8. #define MAXN 1000
  9. #define INF 0xfffffff
  10. using namespace std;
  11. struct node
  12. {
  13. int x,y;
  14. } s,e;
  15. int step[MAXN][MAXN];
  16. int vis[MAXN][MAXN];
  17. //搜索方向
  18. int dir1[8][2]= {
  19. {-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1},{-1,0}};//八方向
  20. int dir2[4][2]= {
  21. {-1,0},{0,1},{1,0},{0,-1}};//四方向直走
  22. int dir3[4][2]= {
  23. {-1,-1},{1,-1},{1,1},{-1,1}};//四方向斜走
  24. /*
  25. 王:横、直、斜都可以走,但每步限走一格。
  26. 后:横、直、斜都可以走,每步格数不受限制。
  27. 车:横、竖均可以走,不能斜走,格数不限。
  28. 象:只能斜走,格数不限。*/
  29. void bfs()
  30. {
  31. bool flag=false;
  32. //王:横、直、斜都可以走,但每步限走一格
  33. memset(step,0,sizeof(step));
  34. memset(vis,false,sizeof(vis));
  35. queue<node>q;
  36. q.push(s);
  37. vis[s.x][s.y]=true;
  38. while(!q.empty())
  39. {
  40. node t=q.front();
  41. q.pop();
  42. for(int i=0; i<8; ++i)
  43. {
  44. node a;
  45. a.x=t.x+dir1[i][0];
  46. a.y=t.y+dir1[i][1];
  47. if(a.x>=0&&a.y>=0&&a.x<8&&a.y<8&&!vis[a.x][a.y])
  48. {
  49. q.push(a);
  50. vis[a.x][a.y]=true;
  51. step[a.x][a.y]=step[t.x][t.y]+1;
  52. }
  53. if(a.x==e.x&&a.y==e.y)
  54. {
  55. vis[t.x][t.y]=true;
  56. step[a.x][a.y]=step[t.x][t.y]+1;
  57. cout<<step[e.x][e.y]<<" ";
  58. flag=true;//标记可以到达
  59. goto B;
  60. }
  61. }
  62. }
  63. if(!flag) cout<<"Inf ";//无法到达
  64. B://后:横、直、斜都可以走,每步格数不受限制。
  65. flag=false;
  66. memset(step,0,sizeof(step));
  67. memset(vis,false,sizeof(vis));
  68. while(!q.empty()) q.pop();//注意清空队列
  69. q.push(s);
  70. vis[s.x][s.y]=true;
  71. while(!q.empty())
  72. {
  73. node t=q.front();
  74. q.pop();
  75. for(int i=0; i<8; ++i)
  76. {
  77. node a;
  78. a.x=t.x+dir1[i][0];//先走一步
  79. a.y=t.y+dir1[i][1];
  80. while(1)//每步格数不受限制
  81. {
  82. if(a.x<0||a.y<0||a.x>=8||a.y>=8) break;//超出限制
  83. if(a.x>=0&&a.y>=0&&a.x<8&&a.y<8&&!vis[a.x][a.y])
  84. {
  85. q.push(a);
  86. vis[a.x][a.y]=true;
  87. step[a.x][a.y]=step[t.x][t.y]+1;
  88. }
  89. if(a.x==e.x&&a.y==e.y)
  90. {
  91. vis[t.x][t.y]=true;
  92. step[a.x][a.y]=step[t.x][t.y]+1;
  93. cout<<step[e.x][e.y]<<" ";
  94. flag=true;
  95. goto C ;
  96. }
  97. a.x+=dir1[i][0];//可以在该方向上继续走
  98. a.y+=dir1[i][1];
  99. }
  100. }
  101. }
  102. if(!flag) cout<<"Inf ";
  103. C://车:横、竖均可以走,不能斜走,格数不限。
  104. flag=false;
  105. memset(step,0,sizeof(step));
  106. memset(vis,false,sizeof(vis));
  107. while(!q.empty()) q.pop();
  108. q.push(s);
  109. vis[s.x][s.y]=true;
  110. while(!q.empty())
  111. {
  112. node t=q.front();
  113. q.pop();
  114. for(int i=0; i<4; ++i)
  115. {
  116. node a;
  117. a.x=t.x+dir2[i][0];
  118. a.y=t.y+dir2[i][1];
  119. while(1)
  120. {
  121. if(a.x<0||a.y<0||a.x>=8||a.y>=8) break;
  122. if(a.x>=0&&a.y>=0&&a.x<8&&a.y<8&&!vis[a.x][a.y])
  123. {
  124. q.push(a);
  125. vis[a.x][a.y]=true;
  126. step[a.x][a.y]=step[t.x][t.y]+1;
  127. }
  128. if(a.x==e.x&&a.y==e.y)
  129. {
  130. vis[a.x][a.y]=true;
  131. step[a.x][a.y]=step[t.x][t.y]+1;
  132. cout<<step[e.x][e.y]<<" ";
  133. flag=true;
  134. goto D ;
  135. }
  136. a.x+=dir2[i][0];
  137. a.y+=dir2[i][1];
  138. }
  139. }
  140. }
  141. if(!flag) cout<<"Inf ";
  142. D: //象:只能斜走,格数不限
  143. flag=false;
  144. memset(step,0,sizeof(step));
  145. memset(vis,false,sizeof(vis));
  146. while(!q.empty()) q.pop();
  147. q.push(s);
  148. vis[s.x][s.y]=true;
  149. while(!q.empty())
  150. {
  151. node t=q.front();
  152. q.pop();
  153. for(int i=0; i<4; ++i)
  154. {
  155. node a;
  156. a.x=t.x+dir3[i][0];
  157. a.y=t.y+dir3[i][1];
  158. while(1)
  159. {
  160. if(a.x<0||a.y<0||a.x>=8||a.y>=8) break;
  161. if(a.x>=0&&a.y>=0&&a.x<8&&a.y<8&&!vis[a.x][a.y])
  162. {
  163. q.push(a);
  164. vis[a.x][a.y]=true;
  165. step[a.x][a.y]=step[t.x][t.y]+1;
  166. }
  167. if(a.x==e.x&&a.y==e.y)
  168. {
  169. vis[a.x][a.y]=true;
  170. step[a.x][a.y]=step[t.x][t.y]+1;
  171. cout<<step[e.x][e.y]<<endl;
  172. flag=true;
  173. return ;
  174. }
  175. a.x+=dir3[i][0];
  176. a.y+=dir3[i][1];
  177. }
  178. }
  179. }
  180. if(!flag) cout<<"Inf"<<endl;
  181. }
  182. int main()
  183. {
  184. #ifdef ONLINE_JUDGE
  185. #else
  186. freopen("G:/cbx/read.txt","r",stdin);
  187. //freopen("G:/cbx/out.txt","w",stdout);
  188. #endif
  189. ios::sync_with_stdio(false);
  190. cin.tie(0);
  191. int T;
  192. cin>>T;
  193. while(T--)
  194. {
  195. char ch;
  196. int t;
  197. cin>>ch>>t;
  198. s.y=ch-'a',s.x=t-1;
  199. cin>>ch>>t;
  200. e.y=ch-'a',e.x=t-1;
  201. if(s.x==e.x&&s.y==e.y) cout<<"0 0 0 0"<<endl;//注意同起终点时必须特判
  202. else bfs();
  203. }
  204. return 0;
  205. }

发表评论

表情:
评论列表 (有 0 条评论,179人围观)

还没有评论,来说两句吧...

相关阅读