90分8WA求助

Damn_wu @ 2024-09-01 14:04:04

#include<iostream>
using namespace std;
int map[500][500];
void set()
{
    for (int i = 0; i < 500; i++)
    {
        for (int j = 0; j < 500; j++)
        {
            map[i][j] = -2;
        }
    }
}
void set2(int a, int b)
{
    for (int i = 1; i <= a; i++)
    {
        for (int j = 1; j <= b; j++)
        {
            map[i][j] = -1;
        }
    }
}
int m1[] = {2,2,1,1,-1,-1,-2,-2};
int m2 [] = {1,-1,2,-2,2,-2,1,-1};
int quex[10000] = { 0 };
int quey[10000] = { 0 };
int main()
{
    set();
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    set2(n, m);
    int head = 0;
    int tail = 1;
    quex[0] = x;
    quey[0] = y;
    map[x][y] = 0;
    do
    {
        for (int i = 0; i < 8; i++)
        {
            if (map[quex[head] + m1[i]][quey[head] + m2[i]] == -1)
            {
                quex[tail] = quex[head] + m1[i];
                quey[tail] = quey[head] + m2[i];
                tail++;
                map[quex[head] + m1[i]][quey[head] + m2[i]] = map[quex[head]][quey[head]]+1;
                //cout << count << "??" << quex[head] + m1[i] << quey[head] + m2[i]<<endl;
            }
        }
        head++;
    } while (head < tail);

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                cout << map[i][j]<<" ";
            }cout << endl;
        }

    return 0;
}

by hanxiaofensheng @ 2024-09-01 14:11:14

#include<bits/stdc++.h>
using namespace std;
queue<int>q,q1;
int a[401][401],ans[401][401];
int dx[8]={-2,-2,2,2,1,-1,1,-1}, dy[8]={-1,1,-1,1,2,-2,-2,2};
int main(){
    memset(ans,-1,sizeof(ans));
    int n,m,x,y;
    cin>>n>>m>>x>>y;
    q.push(x);
    q1.push(y);
    ans[x][y]=0;
    a[x][y]=1;
    while(!q.empty()){
        for(int i=0;i<8;i++){
            int tx=q.front()+dx[i];
            int ty=q1.front()+dy[i];
            if(tx>0&&tx<=n&&ty>0&&ty<=m&&a[tx][ty]==0){
                a[tx][ty]=1;
                ans[tx][ty]=ans[q.front()][q1.front()]+1;
                q.push(tx);
                q1.push(ty);
            }
        }
        q.pop();
        q1.pop();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%-5d",ans[i][j]);
        }
        printf("\n");
    }
    return 0;
}

求关注

by firefly13163 @ 2024-09-01 14:16:34

数组开小了，400*400可能有160000个元素入队

#include<iostream>
using namespace std;
int map[500][500];
void set()
{
    for (int i = 0; i < 500; i++)
    {
        for (int j = 0; j < 500; j++)
        {
            map[i][j] = -2;
        }
    }
}
void set2(int a, int b)
{
    for (int i = 1; i <= a; i++)
    {
        for (int j = 1; j <= b; j++)
        {
            map[i][j] = -1;
        }
    }
}
int m1[] = {2,2,1,1,-1,-1,-2,-2};
int m2 [] = {1,-1,2,-2,2,-2,1,-1};
int quex[160000] = { 0 };
int quey[160000] = { 0 };
int main()
{
    set();
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    set2(n, m);
    int head = 0;
    int tail = 1;
    quex[0] = x;
    quey[0] = y;
    map[x][y] = 0;
    do
    {
        for (int i = 0; i < 8; i++)
        {
            if (map[quex[head] + m1[i]][quey[head] + m2[i]] == -1)
            {
                quex[tail] = quex[head] + m1[i];
                quey[tail] = quey[head] + m2[i];
                tail++;
                map[quex[head] + m1[i]][quey[head] + m2[i]] = map[quex[head]][quey[head]]+1;
                //cout << count << "??" << quex[head] + m1[i] << quey[head] + m2[i]<<endl;
            }
        }
        head++;
    } while (head < tail);

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                    printf("%-5d",map[i][j]);
            }cout << endl;
        }

    return 0;
}

by hjb13357896690 @ 2024-09-01 14:29:35

@qwq13163 问一下为什么到不了中间

by firefly13163 @ 2024-09-01 15:18:30

@hjb13357896690

广搜的特性是先进先出，所以先更新的点是最优步数，当一个点不再更新周围的点时说明越界了或之前更新过了，所以一个点如果更新不到说明没有点能到达，这个是有正确性的，可以用象棋模拟一下

by hjb13357896690 @ 2024-09-01 16:05:52

@qwq13163 栓Q

by Damn_wu @ 2024-09-01 20:34:14

@qwq13163 确实是开小了，感谢感谢