萌新求助43分

回复帖子

@我恰柠檬 2020-08-01 23:21 回复

rt

#include<bits/stdc++.h>
using namespace std;
struct tel
{
    int x,y;
}tl1[35],tl2[35];//传送器的标记
bool tlf[35];//是否标记过这个传送器
struct node
{
    int x,y;
    int step;
}s;//起始点
queue<node>q;
int n,m;
char ma[305][305];
int dir[10][10]={{-1,0},{1,0},{0,1},{0,-1}};
int vis[305][305];
int bfs(node s)
{
    node e,t;
    q.push(s);
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        if(ma[t.x][t.y]<'A' || ma[t.x][t.y]>'Z')//传送器在传送过一次之后走出一格再回去有可能可以走出另外的方向,所以不作visited标记
            vis[t.x][t.y]=1;
        if(ma[t.x][t.y]=='=')
            return t.step;//找到出口就直接return
        for(int i=0;i<4;i++)
        {
            e.x=t.x+dir[i][0];
            e.y=t.y+dir[i][1];
            if(e.x>=1 && e.x<=n && e.y>=1 && e.y<=m && ma[e.x][e.y]!='#' && vis[e.x][e.y]==0)//判断是否是可走的格子
            {
                if(ma[e.x][e.y]>='A' && ma[e.x][e.y]<='Z')//如果是传送器
                {
                    if(e.x==tl1[ma[e.x][e.y]-'A'].x && 
                    e.y==tl1[ma[e.x][e.y]-'A'].y)//如果在传送器的A点
                    {
                        char c=ma[e.x][e.y];
                        e.x=tl2[c-'A'].x;
                        e.y=tl2[c-'A'].y;
                    }//传送到B点
                    else if(e.x==tl2[ma[e.x][e.y]-'A'].x && 
                       e.y==tl2[ma[e.x][e.y]-'A'].y)//如果在传送器的B点
                    {
                        char c=ma[e.x][e.y];
                        e.x=tl1[c-'A'].x;
                        e.y=tl1[c-'A'].y;
                    }//传送到A点
                }
                e.step=t.step+1;
                q.push(e);
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>ma[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)//扫一遍,扫出起始点,标记上传送器
        {
            if(ma[i][j]=='@')
                s.x=i,s.y=j,s.step=0;
            if(ma[i][j]>='A' && ma[i][j]<='Z' && !tlf[ma[i][j]-'A'])
            {
                tl1[ma[i][j]-'A'].x=i;
                tl1[ma[i][j]-'A'].y=j;
                char c=ma[i][j];
                for(int k=i;k<=n;k++)
                {
                    for(int l=j;l<=m;l++)
                    {
                        if(c==ma[k][l] && (k!=i || l!=j))
                        {
                            tl2[ma[i][j]-'A'].x=k;
                            tl2[ma[i][j]-'A'].y=l;
                            break;
                        }
                    }
                }
                tlf[ma[i][j]-'A']=true;
            }
        }
    printf("%d",bfs(s));//bfs
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。