强行bfs,还是WA了第二个点,殊不知哪里还有漏洞,dalao帮忙瞅一哈!

P1434 [SHOI2002] 滑雪

turing_lk @ 2021-06-03 20:48:57

#include<iostream>
using namespace std;
int arr[105][105];
int _x[4]={0,1,0,-1};
int _y[4]={1,0,-1,0};
int ans[105][105];
int const sss=1e9;
struct node
{
    int x,y;
    int step;
}q[1000008];
int f=1,e=0;
int main()
{
    int r,c;
    cin>>r>>c;
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)   cin>>arr[i][j];
    }
    for(int i=1;i<=r;i++)
    {
        arr[i][0]=sss;
        arr[i][c+1]=sss;
    }
    for(int j=1;j<=c;j++)
    {
        arr[0][j]=sss;
        arr[r+1][j]=sss;
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            int sum=0;
            for(int k=0;k<4;k++)
            {
                int dx=i+_x[k];
                int dy=j+_y[k];
                if(arr[i][j]<=arr[dx][dy])
                {
                    sum++;
                }
            }
            if(sum==4)
            {
                q[++e].x=i;
                q[e].y=j;
                q[e].step=1;
            } 
        }
    }
    while(f<=e)
    {
        for(int i=0;i<4;i++)
        {
            int dx=q[f].x+_x[i];
            int dy=q[f].y+_y[i];
            if(dx>0&&dx<=r&&dy>0&&dy<=c&&arr[q[f].x][q[f].y]<arr[dx][dy])
            {
                q[++e].x=dx;
                q[e].y=dy;
                q[e].step=q[f].step+1;
            }
        }
        f++;
        //cout<<f<<" "<<e<<endl;
    }
    cout<<q[e].step;
    return 0;
} 

by httcl @ 2021-06-03 20:50:57

我不是大佬,所以我不知道!HAHA

by 假的螺丝 @ 2021-06-06 09:46:48

1~72行都有问题(doge)


by 林子浩 @ 2021-06-09 20:02:39

bfs才30分的蒟蒻路过


by 纯天然绿色AC @ 2021-09-05 11:34:13

这个程序我看了很多遍,经过我深思熟虑后,我感觉这个程序有问题,因为我不是dalao


by stupidest @ 2022-08-05 15:52:01

让我康康


by stupidest @ 2022-08-05 15:56:39

好像爆搜必卡一个点


|