POJ 3009 Curling 2.0

题目链接：https://vjudge.net/problem/POJ-3009

题目大意：

　　冰壶比赛。

给定一个 n * m 的矩阵A，其中：

A[i][j] == 0，代表通路。
A[i][j] == 1，代表冰块。
A[i][j] == 2，代表冰壶起点。
A[i][j] == 3，代表冰壶所要到达的点。

冰壶只能往上下左右四个方向移动，且碰到冰块才会停下来，同时冰块也会碎掉，冰壶也随之停在原地，冰壶一旦打出界，比赛就结束了，冰壶只要在10步以内经过终点，就算成功。

求每场冰壶比赛的最小移动步数。

分析：

　　dfs基础题，读懂题目最重要。

代码如下：

  1 //#include <bits/stdc++.h>
  2 
  3 // POJ 用 start 
  4 #include<cstdio>  
  5 #include<cstring>  
  6 #include<algorithm>  
  7 #include<iostream>  
  8 #include<string>  
  9 #include<vector>  
 10 #include<stack>  
 11 #include<bitset>  
 12 #include<cstdlib>  
 13 #include<cmath>  
 14 #include<set>  
 15 #include<list>  
 16 #include<deque>  
 17 #include<map>  
 18 #include<queue>  
 19 // POJ 用 end 
 20 
 21 using namespace std;
 22 
 23 /*-------------------Define Start-------------------*/
 24 typedef bool BL;                        // 布尔类型
 25 typedef char SB;                        // 有符号1字节,8位
 26 typedef unsigned char UB;                // 无符号1字节,8位
 27 typedef short SW;                        // 有符号短整型,16位
 28 typedef unsigned short UW;                // 无符号短整型,16位
 29 typedef long SDW;                        // 有符号整型,32位
 30 typedef unsigned long UDW;               // 无符号整型,32位
 31 typedef long long SLL;                    // 有符号长整型,64位
 32 typedef unsigned long long ULL;            // 无符号长整型,64位
 33 typedef char CH;                        // 单个字符
 34 typedef float R32;                        // 单精度浮点数
 35 typedef double R64;                        // 双精度浮点数
 36 
 37 #define Rep(i, n) for (register SDW i = 0; i < (n); ++i)
 38 #define For(i, s, t) for (register SDW i = (s); i <= (t); ++i)
 39 #define rFor(i, t, s) for (register SDW i = (t); i >= (s); --i)
 40 #define foreach(i, c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
 41 #define ms0(a) memset(a,0,sizeof(a))
 42 #define msI(a) memset(a,0x7f,sizeof(a))
 43 #define LOWBIT(x) ((x)&(-x))
 44 
 45 #define MP make_pair
 46 #define PB push_back
 47 #define ft first
 48 #define sd second
 49 
 50 #define pr(x) cout << #x << " = " << x << "  "
 51 #define prln(x) cout << #x << " = " << x << endl
 52 
 53 const ULL mod = 1e9 + 7;                //常用模数(可根据题目需要修改)
 54 const ULL inf = 0x7fffffff;                //用来表示无限大
 55 const ULL infLL = 0x7fffffffffffffffLL;    //用来表示无限大
 56 /*-------------------Define End-------------------*/
 57 
 58 struct Point{
 59     SDW X, Y;
 60     
 61     Point(SDW x = 0, SDW y = 0) : X(x), Y(y) {}
 62     
 63     void set(SDW x, SDW y) {
 64         X = x;
 65         Y = y;
 66     }
 67     
 68     Point operator+ (const Point& x) { return Point(X + x.X, Y + x.Y); }
 69     BL operator== (const Point& x) const { return X == x.X && Y == x.Y; }
 70     BL operator!= (const Point& x) const { return !(*this == x); }
 71 }; 
 72 
 73 const UDW maxN = 2e1 + 7;
 74 SDW N, M;
 75 SDW field[maxN][maxN];
 76 Point S, G;
 77 Point dir[] = {Point(0, -1), Point(-1, 0), Point(0, 1), Point(1, 0)};
 78 SDW ans;
 79 
 80 void input(){
 81     ans = inf;
 82     Rep(i, N) {
 83         Rep(j, M) {
 84             cin >> field[i][j];
 85             if(field[i][j] == 2) {
 86                 S.set(i, j);
 87             }
 88             if(field[i][j] == 3) {
 89                 G.set(i, j);
 90             }
 91         }
 92     }
 93 }
 94 
 95 BL isPass(Point x, Point y) {
 96     if(x.X == y.X) {
 97         return x.X == G.X && min(x.Y, y.Y) <= G.Y && G.Y <= max(x.Y, y.Y);
 98     }
 99     else {
100         return x.Y == G.Y && min(x.X, y.X) <= G.X && G.X <= max(x.X, y.X);
101     }
102 } 
103 
104 // 查找冰壶所能移动到的最左位置 
105 Point leftMost(Point x) {
106     while(x.Y > 0 && field[x.X][x.Y - 1] != 1) {
107         --x.Y;
108     }
109     return x;
110 }
111 
112 // 查找冰壶所能移动到的最上位置 
113 Point upMost(Point x) {
114     while(x.X > 0 && field[x.X - 1][x.Y] != 1) {
115         --x.X;
116     }
117     return x;
118 }
119 
120 // 查找冰壶所能移动到的最右位置 
121 Point rightMost(Point x) {
122     while(x.Y < M - 1 && field[x.X][x.Y + 1] != 1) {
123         ++x.Y;
124     }
125     return x;
126 }
127 
128 // 查找冰壶所能移动到的最下位置 
129 Point downMost(Point x) {
130     while(x.X < N - 1 && field[x.X + 1][x.Y] != 1) {
131         ++x.X;
132     }
133     return x;
134 }
135 
136 Point (*func[4])(Point) = {leftMost, upMost, rightMost, downMost};
137 
138 void dfs(Point p, SDW cnt) {
139     if(cnt > 10) {
140         return;
141     }
142     
143     Rep(i, 4) {
144         Point nextP = func[i](p);        // 冰壶的下一个出发点 
145         Point blockP = nextP + dir[i];    // 冰壶撞到的冰块的位置或者边界位置 
146         
147         if(isPass(p, nextP)) {             // 经过了目标点 
148             ans = min(ans, cnt + 1);
149             return;
150         }
151         if(p != nextP && blockP.X >= 0 && blockP.X < N && blockP.Y >= 0 && blockP.Y < M) {
152             field[blockP.X][blockP.Y] = 0;
153             dfs(nextP, cnt + 1);
154             field[blockP.X][blockP.Y] = 1;
155         }
156     }
157 }
158 
159 void solve(){
160     dfs(S, 0);
161     if(ans > 10) {
162         ans = -1;
163     }
164 }
165 
166 void output(){
167     cout << ans << endl;
168 }
169 
170 int main() {
171     while((cin >> M >> N) && M) {
172         input();
173         solve();
174         output();
175     }
176     return 0;
177 }

View Code