poj 1915 Knight Moves【BFS】【简单】

待我称王封你为后i 2022-08-10 09:29 49阅读 0赞

Knight Moves

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 30000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 23541</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 11059</td> 
  </tr> 
 </tbody> 
</table>

Description

![1915_1.jpg][]

题目大意：输入N，表示棋盘大小为N\*N，在输入两个坐标，分别是起始点与目标点，问从起始点到目标点的最少步数【马的行走规则与国际象棋中的一样】，

Sample Input

3
    8
    0 0
    7 0
    100
    0 0
    30 50
    10
    1 1
    1 1

Sample Output

5
    28
    0

已Accept代码【c++提交】

#include <cstdio>
    #include <queue>
    #include <cstring>
    using namespace std;
    
    int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
    int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};
    int n;
    int dis[301][301];
    int a, b, x, y;
    typedef struct node{
    	int x, y;
    	node() {}
    	node(int x, int y) : x(x), y(y) {}
    }node;
    
    
    void BFS() {
    	queue <node> Q;
    	memset(dis, 0x3f3f3f3f, sizeof(dis));
    	Q.push(node(a, b));
    	dis[a][b] = 0;
    	while(!Q.empty()) {
    		node k = Q.front();
    		Q.pop();
    		int r = k.x;
    		int c = k.y;
    		int ok = 0;
    		for(int i = 0; i < 8; i++) {
    			int nx = r + dx[i];
    			int ny = c + dy[i];
    			if(nx < 0 || nx >=n || ny < 0 || ny >= n)
    				continue;
    			if(dis[nx][ny] > dis[r][c] + 1) {
    				dis[nx][ny] = dis[r][c] + 1;
    				Q.push(node(nx, ny));
    			}
    		}
    	}
    	printf("%d\n", dis[x][y]);
    }
    
    int main() {
    	int t;
    	scanf("%d", &t);
    	while(t--) {
    		scanf("%d", &n);
    		scanf("%d%d%d%d", &a, &b, &x, &y);
    		BFS();
    	}
    	return 0;
    }

[1915_1.jpg]: /images/20220731/230c2da7e3a9459f863f11a9ea72347d.png