求助 WA七十分代码求调

P1649 [USACO07OCT] Obstacle Course S

_Mikasa @ 2023-03-16 15:28:20

#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,0, 0,1,-1};
int dy[5]={0,1,-1,0, 0};
int n,m;
int sx,sy,e1,e2;
int mp[1000][1000];
int vis[1000][1000];
bool Noway(int nx,int ny)
{
    if(nx<1||ny<1||nx>n||ny>n) return true;
    if(vis[nx][ny]==1||mp[nx][ny]==-1) return true;
    return false;
}
struct st
{
    int s,x,y,fa;
    bool operator < (const st &a) const 
    {   
        return s>a.s;
    }
};
int bfs(int x,int y)
{
    priority_queue <st> q;
    st cur;
    cur.s=0;cur.x=x;cur.y=y;cur.fa=100;
    q.push(cur);
    vis[x][y]=1;
    while(!q.empty())
    {
        cur=q.top();
        q.pop();
        if(cur.x==e1&&cur.y==e2)
        {
            return cur.s;
        }
        for(int i=1;i<=4;i++)
        {
            int nx=cur.x+dx[i];
            int ny=cur.y+dy[i];
            if(Noway(nx,ny)) continue;
            vis[nx][ny]=1;
            st nxt;
            nxt.x=nx;
            nxt.y=ny;
            nxt.s=cur.s;
            if(cur.fa!=i) nxt.s++;
            nxt.fa=i;
            q.push(nxt);
        }
    }
    return 0;
}
int main()
{
    cin>>n;
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            char t;
            cin>>t;
            if(t=='A') sx=i,sy=j;
            if(t=='B') e1=i,e2=j;
            if(t=='x') mp[i][j]=-1;
        }
    }
    cout<<bfs(sx,sy)-1;
    return 0;
}

by mashduihca @ 2023-03-16 16:43:59

@_Mikasa 问你个问题,你有没有考虑过,如果对于一个位置,存在两种步数相同但朝向不同的走法,你的vis是无法区分的。


by _Mikasa @ 2023-03-16 16:50:33

@mashduihca 改好了 谢谢大佬%%%

我是:


by mashduihca @ 2023-03-16 16:52:27

@_Mikasa 别急。你是不是没图了。


by _Mikasa @ 2023-03-16 16:54:09

@mashduihca 想什么呢


by mashduihca @ 2023-03-16 16:55:42

@_Mikasa 我有832张顶针图。


by _Mikasa @ 2023-03-16 16:57:24

@mashduihca


by Caiest_Oier @ 2023-03-16 17:08:18

怎么又斗起图了


by _Mikasa @ 2023-03-16 17:17:08

@Caiest_Oier (


by Caiest_Oier @ 2023-03-16 17:19:58

@_Mikasa 你今天上午是不是JC了twc的号,然后私信叫我给你改


by _Mikasa @ 2023-03-16 17:23:00

@Caiest_Oier 不不不 这个是twc太害羞了不好意思发帖子他让我帮他问


| 下一页