http://tjuacm.chaosheng.top/problem.php?id=1282
https://www.luogu.com.cn/problem/P1443
这个题一开始没看懂,因为它没说马可以怎么走,然后按照正常的应该每个都能到,所以和答案不一样。就去搜了一下这个题。
https://my.oschina.net/u/4312789/blog/4688760
里面说马是按“马走日”走的。
理解了之后写了代码,但是第一次提交WA,发现是没有按输出格式,可以看一下参考链接里是怎么解释的,改了输出格式后AC
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 410; int n, m; int mx,my;//马的坐标,M的坐标 int matrix[N][N]; int dx[8] = {1,2,-1,-2,-1,-2,1,2}; int dy[8] = {2,1,2,1,-2,-1,-2,-1}; struct pos{ int x, y; }; void bfs(int x, int y){ queue<pos> q; pos f, v; f.x = x; f.y = y; matrix[f.x][f.y] = 0; q.push(f); while(!q.empty()){ f = q.front(); q.pop(); for(int i = 0; i < 8; i++){ v.x = f.x + dx[i]; v.y = f.y + dy[i]; if(v.x >= 0 && v.x < n && v.y >= 0 && v.y < m && matrix[v.x][v.y] == -1) { matrix[v.x][v.y] = matrix[f.x][f.y] + 1; q.push(v); } } } } int main(){ while(cin >> n >> m >> mx >> my){ memset(matrix, -1, sizeof(matrix)); bfs(mx - 1, my - 1); //bfs(mx, my); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ printf("%-5d", matrix[i][j]); } printf("\n"); } } return 0; }
惊了,TJU和洛谷的输出要求不一样,在tjuoj上提交是格式错误,还要改一下。AC
for(int i = 0; i < n; i++){ for(int j = 0; j < m-1; j++){ //printf("%-5d", matrix[i][j]); printf("%d ", matrix[i][j]); } printf("%d\n", matrix[i][m-1]); } } return 0; }