马的遍历 为什么0分？？？

问题讨论区 基础段
1

2. 马的遍历

题目ID：9563必做题100分

最新提交：

Wrong Answer

0 分

历史最高：

Wrong Answer

0 分

时间限制: 1000ms

空间限制: 131072kB

题目描述

时间限制：1s 空间限制：128M

题目描述：

有一个 n×m 的棋盘，在某个点 (x, y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式：

一行四个数据，分别为 n, m, x, y，代表棋盘的大小和马的坐标。 (1 ≤ x ≤ n ≤ 400, 1 ≤ y ≤ m ≤ 400)

输出格式：

一个 n*m 的矩阵，代表马到达某个点最少要走的步数（不能到达的位置输出 -1）

[image]

样例输入：

3 3 1 1

样例输出：

0 3 2 3 -1 1 2 1 4

#include<bits/stdc++.h>
using namespace std;
int maxa = 0, fx[8]={2,1,1,2,-2,-1,-1,-2 }, fy[8]={-1,-2,2,1,-1,-2,2,1}, a, s,  l[410][410] = {},x,y;
int o[410][410];
queue<int>q;
void bfs() {
    while (!q.empty()) {
        x = q.front();
        q.pop();
        y = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int xx = x + fx[i], yy = y + fy[i];
            if (xx>=1&&yy>=1&&xx<a&&yy<s&&o[xx][yy]==-1) {
                o[xx][yy] = o[xx][yy]+1;
                q.push(xx);
                q.push(yy);
            }
        }
    }
}
int main()
{
    cin >> a >> s >> x >> y;
    memset(o, -1, sizeof o);
    o[x][y]=0;
    q.push(x);
    q.push(y);
    bfs();
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= s; j++) {
            cout << o[i][j]<<" ";
        }
        cout << endl;
    }
    return 0;
}
2 个赞
2

你样例都没过

4 个赞
3

YES

3 个赞
4

不知道为什么

3 个赞
5

？？
这写的什么

3 个赞
6

方案数+1

3 个赞
7

最少的步数，跟方案数有什么关系？

3 个赞
8

:disappointed_relieved::disappointed_relieved::disappointed_relieved:

3 个赞
9

那怎么写

3 个赞
10

你queue都不用结构体的

3 个赞
11

你用结构体维护上一步的步数

3 个赞
12

额。。。

3 个赞
13 
struct node 
{
    int x, y, sum;
};
3 个赞
14

别发AC code

3 个赞
15 
#include <bits/stdc++.h>  
using namespace std;  
int n,m,sx,sy;  
int xx[]={1,2,2,1,-1,-2,-2,-1};  
int yy[]={-2,-1,1,2,2,1,-1,-2};  
int vis[505][505];  
int dist[505][505];//存储
struct node{  
    int x,y,step;  
};  //定义结构体，现在的位置
void bfs(){  
    queue<node> q;  
    q.push({sx,sy,0});
    memset(vis,0,sizeof(vis));  
    memset(dist,-1,sizeof(dist));  //初始化
    dist[sx][sy]=0;
    while(!q.empty()){  
        node f=q.front();  
        q.pop();//这个位置只要定义一个结构体变量，不需要什么x,y了
        for (int i=0;i<8;i++){  
            int nx=f.x+xx[i];  
            int ny=f.y+yy[i];  
            if (/*判断条件*/){  
                vis[nx][ny]=1;  
                dist[nx][ny]=f.step+1;  //存储步数
                q.push({nx,ny,f.step+1});  
            }  
        }  
    }  
}  
int main() {  
    cin>>n>>m>>sx>>sy;
    bfs();
    for(int i=1;i<=n;i++){  
        for(int j=1;j<=m;j++){  
            if(sx==i&&sy==j){
                cout<<0<<" ";
                continue;
            }
            cout<<dist[i][j]<<" ";  
        }  
        cout<<endl;  
    }  
    return 0;  
}
5 个赞
16

你就让她填一个空，有用吗

4 个赞
17

@鲁子欣 老师教过广搜了吗？

4 个赞
18

YES，今天教的

3 个赞
19

老师给的模版看看

3 个赞
20 
struct xy {
    int k, w, e;
};
xy now;
void bfs(int x, int y) {
    queue < xy> q;
    q.push(xy{ x,y,0 });
    while (!q.empty()) {
        now = q.front();
        q.pop();
        if (now.k == f && now.w == g) {
            return;
        }
        for (int i = 0; i < 8; i++) {
            int xx = now.k + fx[i], yy = now.w + fy[i];
            if (新点符合条件) {
                o[xx][yy] = 1;
                q.push(xy{ xx,yy,now.e + 1 });
            }
        }
    }
}
3 个赞