BFS WA+TLE 求调
查看原帖
BFS WA+TLE 求调
270854
二叉苹果树楼主2021/11/18 02:14
#include<iostream>
#include<queue>
#include<map>
using namespace std;
struct crood
{
    int x,y,ans;
}st,fi,root;
queue<crood>q;
int walk[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
char a[305][305];
bool vis[305][305];
map<char,crood>mem1;
map<char,crood>mem2;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>a[n][m];
            if(a[n][m]=='@')
                st.x=i,st.y=j;
            else if(a[n][m]=='=')
                fi.x=i,fi.y=j;
            else if(a[n][m]>='A'&&a[n][m]>='Z')
            {
                if(mem1[a[n][m]].ans==0)
                    mem1[a[n][m]].ans=1,mem1[a[n][m]].x=i,mem1[a[n][m]].y=j;
                else
                    mem2[a[n][m]].ans=1,mem2[a[n][m]].x=i,mem2[a[n][m]].y=j;
            }
        }
    st.ans=0;
    q.push((crood)st);
    while(!q.empty())
    {
        crood f=q.front();
        q.pop();
        vis[f.x][f.y]=1;
        if(f.x==fi.x&&f.y==fi.y)
        {
            cout<<f.ans<<endl;
            return 0;
        }
        for(int i=0;i<=3;i++)
        {
            int fx=f.x+walk[i][0];
            int fy=f.y+walk[i][1];
            if(fx>=1&&fx<=n&&fy>=1&&fy<=m&&a[fx][fy]!='#'&&!vis[fx][fy])
            {
                if(a[fx][fy]>='A'&&a[fx][fy]<='Z')
                {
                    if(fx==mem1[a[fx][fy]].x&&fy==mem1[a[fx][fy]].y)
                        fx=mem2[a[fx][fy]].x,fy=mem2[a[fx][fy]].y;
                    else
                        fx=mem1[a[fx][fy]].x,fy=mem1[a[fx][fy]].y;
                }
                q.push((crood){fx,fy,f.ans+1});
            }
        }
    }
    return 0;
}

思路是特殊点分别记录坐标,然后BFS板子写废了

求调

2021/11/18 02:14
加载中...