大佬们，九敏！！

[方浩景]

普及1班下午的比赛第三题
题目描述：

C. 魔兽世界

Problem ID: 1376

Contest ID: 6308

必做题

Wrong Answer

20 分

小A在WOW中是个小术士.作为一名术士,不会单刷副本是相当丢脸的.所谓单刷副本就是单挑BOSS了,这么有荣誉感的事小A怎么会不做呢?于是小A来到了厄运之槌开始了单刷.小A看了看,厄运之槌的地图是一个N*M的矩形（N，M<=100）,上面遍布了小怪和传送门.例如（1表示有小怪，0表示无小怪,大写字母表示传送门,传送门:例如,走到 B 传送门点将传送到另一个 B 传送点（次数无限，但每次进入传送点只传送过去，不会在传送回来）数据保证每个传送门有且仅有相对应的另一个传送门）:

而入口在左上方（1，1）,BOSS却躲在右下方（N，M）.小A非常急切的想要完成单刷然后去向其他那些战士啊盗贼啊不会单刷的职业炫耀炫耀,所以呢,小A绝不会在小怪身上浪费时间(当然是绕开他们),并且想通过传送门尽快到达BOSS身边.看啊看,想啊想,还是没找出最快的路.终于,灵机一动,想什么啊,编程呗!

输入格式：

第一行2个数据：n m；

下面n行，每行m个数（入口点和BOSS点无怪和传送门），表示厄运之槌的地图。地图数据之间无空格。每步只能走一格，方向上下左右。左上角为入口点,右下角为出口点.

输出格式：

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

样例输入一：

3 4 0000 00A0 A000

样例输出一：

4

样例输入二：

4 6 010100 01A100 011101 0000A0

样例输出二：

10

数据范围：

对60%的数据,n,m<=20

对100%的数据,n,m<=100

提示：

样例一路线如图：

样例二：

路线如下：（1，1）-（2，1）-（3，1）-（4，1）-（4，2）-（4，3）-（4，4）-（4，5）（2，3）-（1，3）-（2，3）（4，5）-（4，6）

[方浩景]

感谢大佬

[王梓涵 (梦幻の幸运使者 qwq)]

给个解决方案

[沈子开]

最好还是不要直接发代码吧

[王梓涵 (梦幻の幸运使者 qwq)]

[邹天瑜 (芙芙)]

#include<bits/stdc++.h>
using namespace std;
int n,m,vis[105][105],head=1,tail=0;
char a[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
struct node{
int x,y,step;
};
queue que;
void bfs(int x,int y){
que.push(node{x,y,0});
while(que.size()){
node t=que.front();
que.pop();
if(t.x==n and t.y==m){
cout<<t.step;
exit(0);
}
for(int i=0;i<4;i++){
int tx=dx[i]+t.x;
int ty=dy[i]+t.y;
if(tx<1 or ty<1 or tx>n or ty>m or vis[tx][ty]==1 or a[tx][ty]==‘1’){
continue;
}
if(a[tx][ty]>=‘A’ and a[tx][ty]<=‘Z’){
int xs,ys;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if((tx!=i or ty!=j) and a[tx][ty]==a[i][j]){
xs=i,ys=j;
break;
}
vis[tx][ty]=1;
tx=xs,ty=ys;
que.push(node{xs,ys,t.step+1});
}
else{
vis[tx][ty]=1;
que.push(node{tx,ty,t.step+1});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
vis[1][1]=1;
bfs(1,1);
cout<<“No Solution.”;
return 0;
}

[胡沛旸 (絮影)]

代码记得格式化

[程诺 (【语法】顺序结构)]

回复牢帖是不好的
此话题已被解决

仅在以下情况下回复：

• 您有其他详细信息
• 该解决方案对您不起作用

如果您有不相关的问题，请新建话题。