挑战K神

题目

题目描述

小Y在OIER中是个菜鸟，作为一名菜鸟，如果能挑战K神是个有荣誉感的事
小Y怎么会放过呢？于是小Y来到了OIER们的活动场所——Playground开始了挑战赛
小Y看了看，Playground的地图是一个$N*M$的矩形($N，M\leqslant 100$)，里面遍布了障碍和一些传送带
例如，1表示该位置有障碍，0表示无障碍，大写字母表示传送带
传送带：例如，走到B传送带，将传送到另一个B传送带（次数无限，但每次进入传送带只会传送过去，不会再传送回来）
| 入口 | 0 | 0 | 0 |
|–|–|–|–|
| 0 | 0 | A | 0 |
| A | 0 | 0 | K神 |

输入格式

第一行$2$个数据$n,m$
下面$n$行，每行$m$个数（入口点、K神、障碍、无障碍的空地和传送带），表示Playground的地图。地图数据之间无空格
每步只能走一格，方向为上下左右，左上角为入口点，右下角为出口点(K神）

输出格式

一个整数，表示小Y最少需要走多少步
如果小Y不能走到目标，则输出No Solution.

样例

样例输入

3 4
0000
00A0
A000

样例输出

4

数据范围与提示

样例说明

路线如图：

数据范围

对$60%$的数据：$n,m\leqslant 20$
对$100%$的数据：$n,m\leqslant 100$

题解

基本的搜索题……
就是一个宽搜，记录下所有的传送带的坐标，遇到传送带就直接传送就好了
没有什么好说的了，附上代码：

#include<cstdio>
struct ppap
{
    int x,y,s;
}q[10010];
int n,m,l,r,dx[5]={-1,0,1,0},dy[5]={0,-1,0,1},c1[30][5],c2[30][5],v[110][110];
char map[110][110];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        scanf(" %c",&map[i][j]);
        if(map[i][j]>='A'&&map[i][j]<='Z'){
            if(!c1[map[i][j]-'A'+1][1]) c1[map[i][j]-'A'+1][1]=i,c1[map[i][j]-'A'+1][2]=j;
            else c2[map[i][j]-'A'+1][1]=i,c2[map[i][j]-'A'+1][2]=j;
        }
    }
    r=q[1].x=q[1].y=v[1][1]=1;
    while(l<r){
        int x=q[++l].x,y=q[l].y;
        if(x==n&&y==m){printf("%d",q[l].s);return 0;}
        if(map[x][y]>='A'&&map[x][y]<='Z'){
            int temp=map[x][y]-'A'+1;
            if(c1[temp][1]==x&&c1[temp][2]==y) x=c2[temp][1],y=c2[temp][2];
            else x=c1[temp][1],y=c1[temp][2];
        }
        for(int i=0;i<4;i++){
            int X=x+dx[i],Y=y+dy[i];
            if(X>0&&X<=n&&Y>0&&Y<=m&&(!v[X][Y])&&map[X][Y]!='1') q[++r].x=X,q[r].y=Y,q[r].s=q[l].s+1,v[X][Y]=1;
        }
    }
    printf("No Solution.");
}

喜欢的话，给博主赏一杯冰阔乐吧~