poj3009（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
",minn);
120         else
121             printf("-1
");
122     }
123     return 0;
124 }

View Code