魔兽世界
XJOI - 题目ID:1376必做题100分
最新提交:
Wrong Answer
80 分
历史最高:
Wrong Answer
80 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
小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)
我的代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,sum=10005,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
char s[105][105];
struct bfs{
int x,y,step;
};
struct chuan{
int a,b,c,d;
}ui[30];
void fo(int x,int y){
int vis[105][105] = {0};
vis[1][1] = 1;
queue<bfs> q;
q.push(bfs {x,y,0});
while(!q.empty()){
bfs now = q.front();
for(int i = 0; i<4; i++){
int xx=now.x+dx[i],yy=now.y+dy[i];
int o = s[xx][yy]-'A';
if(xx == n && yy == m){
if(sum>now.step+1){
sum = now.step+1;
}
}else if(o>=0 && o<=25 && vis[xx][yy]<2){
vis[xx][yy]++;
if(xx == ui[o].a && yy == ui[o].b){
xx = ui[o].c;
yy = ui[o].d;
vis[xx][yy]++;
q.push(bfs {xx,yy,now.step+1});
// cout<<ui[o].c<<" "<<ui[o].d<<endl;
}else{
xx = ui[o].a;
yy = ui[o].b;
vis[xx][yy]++;
q.push(bfs {xx,yy,now.step+1});
// cout<<ui[o].a<<" "<<ui[o].b<<endl;
}
}else if(xx>0 && xx<=n && yy>0 && yy<=m && s[xx][yy] != '1' && vis[xx][yy] == 0){
// cout<<xx<<" "<<yy<<" ";
vis[xx][yy]++;
q.push(bfs {xx,yy,now.step+1});
}
}
q.pop();
}
}
int main(){
cin>>n>>m;
for(int i = 1; i<=n; i++){
for(int j = 1; j<=m; j++){
cin>>s[i][j];
int o = s[i][j]-'A';
if(o>=0 && o<=25){
if(ui[o].a!=0){
ui[o].c = i;
ui[o].d = j;
// cout<<o<<" "<<ui[o].c<<" "<<ui[o].d<<endl;
}else{
ui[o].a = i;
ui[o].b = j;
// cout<<o<<" "<<ui[o].a<<" "<<ui[o].b<<endl;
}
}
}
}
// cout<<endl;
fo(1,1);
if(sum == 10005){
cout<<"No Solution";
}else{
cout<<sum;
}
return 0;
}

