求助!蒟蒻C++BFS只有20分!

P1649 [USACO07OCT] Obstacle Course S

swl3992 @ 2019-09-08 15:07:59

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x,y,sum,way;
    node(int x=0,int y=0,int sum=0,int way=0):x(x), y(y),sum(sum),way(way){}
};
int minn=2147483647;
bool vis[105][105][4];
char board[105][105];
int X[]={-1,1,0,0};
int Y[]={0,0,-1,1};
int n,m;
int N,M;
void bfs(int x,int y)
{
    queue<node> q;
    q.push(node(x,y,0,0));
    q.push(node(x,y,0,1));
    q.push(node(x,y,0,2));
    q.push(node(x,y,0,3));
    vis[x][y][0]=true;
    vis[x][y][1]=true;
    vis[x][y][2]=true;
    vis[x][y][3]=true;
    while(!q.empty())
    {
        node f=q.front();
        q.pop();
        if(f.x==N&&f.y==M)
        {
            minn=min(minn,f.sum);
            continue;
        }
        for(int i=0;i<4;i++)
        {
            if((i==0&&f.way==1)||(i==1&&f.way==0)||(i==2&&f.way==3)&&(i==3&&f.way==2))
            {
                continue;
            }
            int xx=f.x+X[i];
            int yy=f.y+Y[i];
            int temp=0;
            if(f.way!=i)
            {
                temp=1;
            }
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&!vis[xx][yy][i]&&board[xx][yy]!='x')
            {
                q.push(node(xx,yy,f.sum+temp,i));
//              cout<<xx<<" "<<yy<<endl;
//              cout<<N<<" "<<M<<endl<<endl;
                vis[xx][yy][i]=true;
            }
        }
    }
}
int main ()
{
    ios::sync_with_stdio(0);
    cin>>n;
    m=n;
    int nn,mm;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>board[i][j];
            if(board[i][j]=='A')
            {
                nn=i;
                mm=j;
            }
            else if(board[i][j]=='B')
            {
                N=i;
                M=j;
            }
        }
    }
//  cout<<nn<<" "<<mm<<" "<<N<<" "<<M<<endl;
    bfs(nn,mm);
    if(minn==2147483647)
    {
        cout<<-1;
    }
    else
    {
        cout<<minn;
    }
    return 0;
}

by Invalid_Operation @ 2020-02-04 23:59:57

为什么要用三维数组...


by yzhid @ 2020-04-07 14:15:50

这样的话,可能需要吧转弯次数也加进标记数组,否则有一些点访问过一次就无法再次访问了


|