3094 寻找sb4

3094 寻找sb4

 

 时间限制: 1 s
 空间限制: 32000 KB
 题目等级 : 黄金 Gold
 
 
题目描述 Description

sb有一天和sml吵架了,她离家出走,走到了一个a*a的正方形里,她迷路了!

A为入口,

B为sb。

正在此时,sml来到了迷宫入口,他和她都很着急,求最快要x步(从入口进,从入口出)(要*2)

‘0’为水,‘1’为路,‘2’为障碍物,‘3’为草地(可以走)。‘4’为树(也走不了),‘5’为石头(可以走)

输入描述 Input Description

a

a*a个数(A,B也在内)

输出描述 Output Description

x(A,B只统计1次)

样例输入 Sample Input

5

0 0 0 0 A

1 1 1 1 1

3 2 4 1 0

5 5 5 5 0

0 0 0 3 B

//画横线的为路径!

样例输出 Sample Output

12

数据范围及提示 Data Size & Hint

a<=500

对于30%的数据只有“1”和“0”。

对于60%的数据没有“3”和“5”

对于100%的数据,路程>=10.

当行不通时“printf(“NoNE!”);”

#include<cstdio>
#include<iostream>
using namespace std;
int sum=0,n,ff=0,x[5]={0,1,0,0,-1},y[5]={0,0,1,-1,0},f[501][501],xx[501],yy[501];
int ans[501][501];
char map[501][501];

int main()
{
int sbx,sby;
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
char r;
f[i][j]=1;
cin>>r;
map[i][j]=r;
if (r=='A') {
xx[1]=i;
yy[1]=j;
f[i][j]=0;
}
if (r=='B'){
sbx=i;
sby=j;
}
if (r=='2'||r=='4'||r=='0') f[i][j]=0;
}
int head=0,tail=1;
while (head!=tail)
{
head++;
int aa=xx[head],bb=yy[head];
for (int i=1;i<=4;i++)
{
int a=xx[head]+x[i],b=yy[head]+y[i];
if (f[a][b]&&a<=n&&a>0&&b<=n&&b>0)
{
f[a][b]=0;
xx[++tail]=a;
yy[tail]=b;
ans[a][b]=ans[aa][bb]+1;
if (a==sbx&&b==sby)
{
ff=1;
break;
}
}
}
}
if (ff) cout<<ans[sbx][sby]*2;
else cout<<"NoNE!";
}

原文地址:https://www.cnblogs.com/xiaoningmeng/p/5261971.html