首页 > 代码库 > POJ 3083 Children of the Candy Corn
POJ 3083 Children of the Candy Corn
题意：给你一个图，告诉你起始点S，终点E，‘.’可走，‘#’不可走。求从起点到终点1.总是先选择向左走的步数。2.总是选择先向右走的步数。3.最短路
思路：
对于第一种和第二种，用深搜，只要写对存方向的数组即可：
int r[4][2]= {{0,-1},{1,0},{0,1},{-1,0}};
int l[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
对于第三种，广搜求最短路：具体见代码~~
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<iomanip> 5 #include<queue> 6 #include<algorithm> 7 using namespace std; 8 struct node 9 { 10 int w; 11 int e; 12 int step; 13 }; 14 int n,m; 15 int vist[50][50]; 16 int r[4][2]= {{0,-1},{1,0},{0,1},{-1,0}}; 17 int l[4][2]= {{0,1},{1,0},{0,-1},{-1,0}}; 18 int dir[4][2]={{0,1},{-1,0},{1,0},{0,-1}}; 19 char map[50][50]; 20 int sx,sy,ex,ey,ans; 21 int dfs1(int x,int y,int step) 22 { 23 if(x==ex&&y==ey) 24 return step+1; 25 if(x<0||x>=n||y<0||y>=m||map[x][y]==‘#‘) 26 return 0; 27 ans=(ans+3)%4; 28 int temp=0; 29 while(1) 30 { 31 temp=dfs1(x+l[ans][0],y+l[ans][1],step+1); 32 if(temp!=0) 33 break; 34 ans=(ans+1)%4; 35 } 36 return temp; 37 } 38 int dfs2(int x,int y,int step) 39 { 40 if(x==ex&&y==ey) 41 return step+1; 42 if(x<0||x>=n||y<0||y>=m||map[x][y]==‘#‘) 43 return 0; 44 ans=(ans+3)%4; 45 int temp=0; 46 while(1) 47 { 48 temp=dfs2(x+r[ans][0],y+r[ans][1],step+1); 49 if(temp!=0) 50 break; 51 ans=(ans+1)%4; 52 } 53 return temp; 54 } 55 int bfs() 56 { 57 memset(vist,0,sizeof(vist)); 58 int i,x,y; 59 struct node p; 60 queue<struct node>Q; 61 p.w=sx; 62 p.e=sy; 63 p.step=1; 64 Q.push(p); 65 vist[sx][sy]=1; 66 while(!Q.empty()) 67 { 68 p=Q.front(); 69 Q.pop(); 70 if(p.w==ex&&p.e==ey) 71 return p.step; 72 for(i=0;i<4;i++) 73 { 74 x=p.w+dir[i][0]; 75 y=p.e+dir[i][1]; 76 if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]!=‘#‘&&vist[x][y]==0) 77 { 78 vist[x][y]=1; 79 struct node t; 80 t.w=x; 81 t.e=y; 82 t.step=p.step+1; 83 Q.push(t); 84 } 85 } 86 } 87 } 88 int main() 89 { 90 int T; 91 scanf("%d",&T); 92 while(T--) 93 { 94 scanf("%d%d",&m,&n); 95 getchar(); 96 for(int i=0; i<n; i++) 97 { 98 for(int j=0; j<m; j++) 99 {100 scanf("%c",&map[i][j]);101 if(map[i][j]==‘S‘)102 {103 sx=i;104 sy=j;105 }106 if(map[i][j]==‘E‘)107 {108 ex=i;109 ey=j;110 }111 }112 getchar();113 }114 ans=0;115 printf("%d ",dfs1(sx,sy,0));116 ans=0;117 printf("%d ",dfs2(sx,sy,0));118 printf("%d\n",bfs());119 }120 return 0;121 }
好好训练不做弱菜~~！
POJ 3083 Children of the Candy Corn
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。