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