首页 > 其他 > 详细

codevs 3094 寻找sb4

时间:2016-03-08 12:03:13      阅读:175      评论:0      收藏:0      [点我收藏+]

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!";
}

  

codevs 3094 寻找sb4

原文:http://www.cnblogs.com/sjymj/p/5253477.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!