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 |
感觉对dfs有更多的理解了1AC#include <iostream> #include <cstdio> #define INF 0x3f3f3f3f using namespace std; const int MAX=22; int map[MAX][MAX]; int n,m; int x1,y1,x2,y2; int fx[]={1,-1,0,0}; int fy[]={0,0,1,-1}; int flag=0; int step; struct node { int x,y; }a; bool move(int x,int y,int i) { a.x=x,a.y=y; if(map[x][y]==3) { flag=1; a.x=x,a.y=y; return true; } if(x<1||x>n||y<1||y>m) return false; if(map[x][y]!=0) return false; while(1) { x+=fx[i]; y+=fy[i]; if(x<1||x>n||y<1||y>m) return false; if(map[x][y]==3) { flag=1; a.x=x,a.y=y; return true; } if(map[x][y]!=0) { return true; } a.x=x,a.y=y; } } void dfs(int x,int y,int ans) { if(ans>10) { return ; } if(flag) { step=min(step,ans); return ; } for(int i=0;i<4;++i) { int tx=x+fx[i]; int ty=y+fy[i]; if(move(tx,ty,i)==false) continue; else { tx=a.x,ty=a.y; if(flag) { // printf("%d %d\n",step,ans); step=min(step,ans); return ; } map[tx+fx[i]][ty+fy[i]]=0; // for(int k=1;k<=n;++k) // { // for(int j=1;j<=m;++j) // printf("%2d",map[k][j]); // printf("\n"); // } dfs(tx,ty,ans+1); map[tx+fx[i]][ty+fy[i]]=1; flag=0; } } } int main() { while(scanf("%d%d",&m,&n)!=EOF) { if(m==0&&n==0) break; step=INF; flag=0; for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { scanf("%d",&map[i][j]); if(map[i][j]==2) { x1=i,y1=j; map[i][j]=0; } if(map[i][j]==3) { x2=i,y2=j; } } } dfs(x1,y1,0); if(step!=INF&&step<=9) printf("%d\n",step+1); else printf("-1\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator