| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
求个犀利测试数据#include <iostream>
#include <cstring>
#include <stdio.h>
#include <queue>
const int maxn=30;
using namespace std;
struct Node{
int x,y,step;
friend bool operator<(Node n1,Node n2)
{
return n1.step>n2.step;
}
};
int w,h,map[maxn][maxn],sx,sy;
int flag;
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
void bfs(int s,int e,int step){
priority_queue<Node> Q;
Node p,q;
p.x=s;p.y=e;p.step=0;
Q.push(p);
while(!Q.empty()){
p=Q.top();
Q.pop();
for(int i=0;i<4&&flag==0;i++){
int xx=p.x+dir[i][0];
int yy=p.y+dir[i][1];
int ans=0;
if(p.step>10) return;
while((xx>=0&&xx<h)&&(yy>=0&&yy<w)){
//如果是空地不能停下
q.step=p.step+1;
if(map[xx][yy]==0){
//cout<<"asd::"<<xx<<" "<<yy<<endl;
q.x=xx;q.y=yy;
}
//撞到block停下
else if(map[xx][yy]==1) {
if(ans!=0){
map[xx][yy]=0;
}Q.push(q);
break;
}
//终点
else if(map[xx][yy]==3){
flag=q.step; return;
}
xx+=dir[i][0];
yy+=dir[i][1];
ans++;
}
}
}
}
int main(){
//freopen("in.txt","r",stdin);
while(cin>>w>>h){
if((w+h)==0) break;
flag=0;
memset(map,0,sizeof(map));
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
cin>>map[i][j];
if(map[i][j]==2){
sx=i;sy=j;
map[i][j]=0;
}
}
}
bfs(sx,sy,0);
if(flag<=10&&flag!=0) cout<<flag<<endl;
else cout<<"-1"<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator