首页 > 代码库 > poj3009(Curling 2.0)
poj3009(Curling 2.0)
题目地址:Curling 2.0
题目大意:
一项在冰上网格的运动,在网格中2为起点,3为终点,1代表着有墙阻挡,0代表空白处。运动员从2点可以沿着上下左右四个方向出发,直至碰到墙才会改变自己的方向,但是注意碰到墙之后,此墙会消失变为空白处,意思是可以下次通过。
解题思路:
因为就四个方向可以枚举深搜。
代码;
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1}; 32 const int diry[]= {-2,-2,-1,-1,1,1,2,2}; 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 34 /***************************************/ 35 void openfile() 36 { 37 freopen("data.in","rb",stdin); 38 freopen("data.out","wb",stdout); 39 } 40 priority_queue<int> qi1; 41 priority_queue<int, vector<int>, greater<int> >qi2; 42 /**********************华丽丽的分割线,以上为模板部分*****************/ 43 int m,n; 44 int map[50][50]; 45 int ex,ey; 46 int minn; 47 int ce; 48 int DFS(int x,int y,int cnt) 49 { 50 if (cnt>10) 51 return 0; 52 int i,j,k; 53 for(i=0; i<4; i++) 54 { 55 int xx=x+d1x[i]; 56 int yy=y+d1y[i]; 57 if (xx>=0&&xx<n&&yy>=0&&yy<m&&map[xx][yy]!=1) 58 { 59 // cnt++; 60 if (xx==ex&&yy==ey) 61 { 62 ce=1; 63 if (minn>cnt) 64 minn=cnt; 65 return 0; 66 } 67 while(1) 68 { 69 xx=xx+d1x[i]; 70 yy=yy+d1y[i]; 71 if (xx==ex&&yy==ey) 72 { 73 ce=1; 74 if (minn>cnt) 75 minn=cnt; 76 return 0; 77 } 78 if (xx<0||xx>=n||yy<0||yy>=m) 79 break; 80 if (map[xx][yy]==1) 81 { 82 map[xx][yy]=0; 83 DFS(xx-d1x[i],yy-d1y[i],cnt+1); 84 map[xx][yy]=1; 85 break; 86 } 87 } 88 } 89 } 90 } 91 int main() 92 { 93 94 while(scanf("%d%d",&m,&n)&&(n+m)) 95 { 96 int i,j; 97 int sx,sy; 98 memset(map,0,sizeof(map)); 99 for(i=0; i<n; i++)100 for(j=0; j<m; j++)101 {102 scanf("%d",&map[i][j]);103 if (map[i][j]==2)104 {105 sx=i;106 sy=j;107 }108 if (map[i][j]==3)109 {110 ex=i;111 ey=j;112 }113 }114 int cnt=0;115 ce=0;116 minn=INF;117 DFS(sx,sy,cnt+1);118 if (ce)119 printf("%d\n",minn);120 else121 printf("-1\n");122 }123 return 0;124 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。