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<cstdio> #include<iostream> #include<queue> #include<cstring> const int N=20+1; using namespace std; int mapp[N][N],vis[N][N],step,ans,w,h; int dx[4]= {1,0,-1,0},dy[4]= {0,1,0,-1}; void dfs(int step,int x,int y) { if(mapp[x][y]==3)ans=min(ans,step); else { if(step<10) { for(int i=0; i<4; i++) for(int j=1;; j++) { if(0<=x+j*dx[i]&&x+j*dx[i]<h&&0<=y+j*dy[i]&&y+j*dy[i]<w&&mapp[x+dx[i]][y+dy[i]]!=1) { if(mapp[x+j*dx[i]][y+j*dy[i]]==1) { mapp[x+j*dx[i]][y+j*dy[i]]=0; dfs(step+1,x+(j-1)*dx[i],y+(j-1)*dy[i]); mapp[x+j*dx[i]][y+j*dy[i]]=1; break; } else if(mapp[x+j*dx[i]][y+j*dy[i]]==3) { dfs(step+1,x+j*dx[i],y+j*dy[i]); break; } } else break; } } } } int main() { int x0,y0; while(cin>>w>>h&&(w+h)) { ans=0x3f3f3f3f; memset(mapp,-1,sizeof(mapp)); for(int i=0; i<h; i++) for(int j=0; j<w; j++) { cin>>mapp[i][j]; if(mapp[i][j]==2) { x0=i; y0=j; mapp[i][j]=0; } } dfs(0,x0,y0); if(ans<=10)cout<<ans<<endl; else cout<<-1<<endl; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator