WA 0 求调

P1443 马的遍历

ltzx_2023_jy @ 2024-12-05 11:46:54

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iomanip>
#include <cstdio>

using namespace std;

const int N = 410;
int stx, sty, n, m;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

struct node{
    int x, y;
    int step;
};

void bfs(int xx, int yy){
    int st[N][N];
    memset(st, 0, sizeof(st));
    queue <node> q;
    node t;
    t.x = stx, t.y = sty, t.step = 0;
    q.push(t);
    while(!q.empty()){
        node u = q.front();
        st[u.x][u.y] = 1;
        q.pop();
        if(u.x == xx && u.y == yy){
            printf("%-5d", u.step);
            return;
        }
        for(int i = 0; i < 8; i ++ ){
            int tx = u.x + dx[i];
            int ty = u.y + dy[i];
            if(st[tx][ty] || tx <= 0 || tx > n || ty <= 0 || ty > n) continue;
            node n;
            n.x = tx;
            n.y = ty;
            n.step = u.step + 1;
            q.push(n);
        }
    }
    printf("%-5d", -1);
}

int main(){
    cin >> n >> m >> stx >> sty;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            bfs(i, j);
        }
        cout << endl;
    }
}

by YBa2Cu3O7 @ 2024-12-05 13:03:02

你这个是在对每个点找能不能从起始位置出发？感觉没有必要，时间复杂度好大。从起始点遍历就好了，遍历途中存一下step。

#include <bits/stdc++.h>
using namespace std;
constexpr array<int,8> mvx{-2,-1,1,2,2,1,-1,-2};
constexpr array<int,8> mvy{1,2,2,1,-1,-2,-2,-1};
int main(){
    int n,m,x,y;
    cin>>n>>m>>x>>y;
    --x;--y;
    vector<vector<int>> G(n,vector<int>(m,-1));
    queue<pair<int,int>> q;
    int step=0;
    G[x][y]=step;
    q.push({x,y});
    auto check=[&](int x,int y){
        return x>=0&&x<n&&y>=0&&y<m&&G[x][y]==-1;//只有-1的是没入队过的
    };
    while(!q.empty()){
        int sz=q.size();
        for(int i=0;i<sz;++i){
            const auto& p=q.front();
            for(int j=0;j<8;++j){
                int u=p.first+mvx[j],v=p.second+mvy[j];
                if(check(u,v)){
                    G[u][v]=-2;//表示已被存入,防止被多次入队
                    q.push({u,v});
                }
            }
            G[p.first][p.second]=step;
            q.pop();
        }
        ++step;
    }
    for(const auto& u:G){
        for(const auto& v:u){
            cout<<v<<' ';
        }
        cout<<'\n';
    }
}