【HDOJ】1254 推箱子

来一发搜索。数据量比较小，这么玩儿都能ac。搞个优先队列。
先扫描从起点可以到达箱子的上下左右中哪些位置，并针对这些位置进行bfs。
所谓推，就是箱子和人同向移动一个单位。bfs的时候注意一些限制条件就好了。
  1 /* 1254 */
  2 #include <iostream>
  3 #include <string>
  4 #include <map>
  5 #include <queue>
  6 #include <set>
  7 #include <stack>
  8 #include <vector>
  9 #include <deque>
 10 #include <algorithm>
 11 #include <cstdio>
 12 #include <cmath>
 13 #include <ctime>
 14 #include <cstring>
 15 #include <climits>
 16 #include <cctype>
 17 #include <cassert>
 18 #include <functional>
 19 #include <iterator>
 20 #include <iomanip>
 21 using namespace std;
 22 //#pragma comment(linker,"/STACK:102400000,1024000")
 23 
 24 #define sti                set<int>
 25 #define stpii            set<pair<int, int> >
 26 #define mpii            map<int,int>
 27 #define vi                vector<int>
 28 #define pii                pair<int,int>
 29 #define vpii            vector<pair<int,int> >
 30 #define rep(i, a, n)     for (int i=a;i<n;++i)
 31 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 32 #define clr                clear
 33 #define pb                 push_back
 34 #define mp                 make_pair
 35 #define fir                first
 36 #define sec                second
 37 #define all(x)             (x).begin(),(x).end()
 38 #define SZ(x)             ((int)(x).size())
 39 #define lson            l, mid, rt<<1
 40 #define rson            mid+1, r, rt<<1|1
 41 
 42 const int maxn = 10;
 43 int M[maxn][maxn];
 44 bool reach[maxn][maxn];
 45 bool visit[maxn][maxn][maxn][maxn];
 46 int dir[4][2] = {
 47     -1,0, 1,0, 0,-1, 0,1
 48 };
 49 int gx, gy, bx, by, hx, hy;
 50 int n, m;
 51 int ans;
 52 
 53 bool judge(int x, int y) {
 54     return x<0 || x>=n || y<0 || y>=m;
 55 }
 56 
 57 void bfs_human() {
 58     queue<pii> Q;
 59     pii p;
 60     int x, y;
 61 
 62     memset(reach, false, sizeof(reach));
 63     reach[hx][hy] = true;
 64     Q.push(mp(hx, hy));
 65 
 66     while (!Q.empty()) {
 67         p = Q.front();
 68         Q.pop();
 69         rep(i, 0, 4) {
 70             x = p.fir + dir[i][0];
 71             y = p.sec + dir[i][1];
 72             if (judge(x, y) || M[x][y]!=0 || reach[x][y])
 73                 continue;
 74             reach[x][y] = true;
 75             Q.push(mp(x, y));
 76         }
 77     }
 78 }
 79 
 80 typedef struct node_t {
 81     int hx, hy;
 82     int bx, by;
 83     int bn;
 84 
 85     node_t() {}
 86 
 87     node_t(int hx, int hy, int bx, int by, int bn):
 88         hx(hx), hy(hy), bx(bx), by(by), bn(bn) {}
 89 
 90     friend bool operator< (const node_t& a, const node_t& b) {
 91         return a.bn > b.bn;
 92     }
 93 
 94     void print() {
 95         printf("hx=%d, hy=%d, bx=%d, by=%d, bn=%d
", hx,hy,bx,by,bn);
 96     }
 97 
 98 } node_t;
 99 
100 // #define DEBUG
101 int bfs(int hx, int hy) {
102     priority_queue<node_t> Q;
103     node_t d(hx, hy, bx, by, 0), nd;
104 
105     memset(visit, false, sizeof(visit));
106     visit[bx][by][hx][hy] = true;
107     Q.push(d);
108 
109     while (!Q.empty()) {
110         nd = Q.top();
111         Q.pop();
112         #ifdef DEBUG
113             nd.print();
114             if (nd.hx==2 && nd.hy==1 && nd.bx==3 && nd.by==1) {
115                 puts("here");
116             }
117         #endif
118         rep(i, 0, 4) {
119             d.hx = nd.hx + dir[i][0];
120             d.hy = nd.hy + dir[i][1];
121             if (judge(d.hx, d.hy) || M[d.hx][d.hy]==1)
122                 continue;
123 
124             // check whether is box
125             if (d.hx==nd.bx && d.hy==nd.by) {
126                 d.bx = nd.bx + dir[i][0];
127                 d.by = nd.by + dir[i][1];
128                 if (judge(d.bx, d.by) || M[d.bx][d.by]==1)
129                     continue;
130                 d.bn = nd.bn + 1;
131             } else {
132                 d.bx = nd.bx;
133                 d.by = nd.by;
134                 d.bn = nd.bn;
135             }
136 
137             if (visit[d.bx][d.by][d.hx][d.hy])
138                 continue;
139 
140             visit[d.bx][d.by][d.hx][d.hy] = true;
141             if (d.bx==gx && d.by==gy)
142                 return d.bn;
143 
144             #ifdef DEBUG
145                 nd.print();
146                 if (d.hx==4 && d.hy==1 && d.bx==3 && d.by==1) {
147                     puts("there");
148                 }
149             #endif
150             Q.push(d);
151         }
152     }
153 
154     return INT_MAX;
155 }
156 
157 void solve() {
158     int x, y, tmp;
159 
160     ans = INT_MAX;
161 
162     bfs_human();
163     rep(i, 0, 4) {
164         x = bx + dir[i][0];
165         y = by + dir[i][1];
166         if (judge(x, y) || M[x][y]==1 || !reach[x][y])
167             continue;
168         tmp = bfs(x, y);
169         ans = min(tmp, ans);
170     }
171 
172     ans = ans==INT_MAX ? -1:ans;
173     printf("%d
", ans);
174 }
175 
176 int main() {
177     ios::sync_with_stdio(false);
178     #ifndef ONLINE_JUDGE
179         freopen("data.in", "r", stdin);
180         freopen("data.out", "w", stdout);
181     #endif
182 
183     int t;
184 
185     scanf("%d", &t);
186     while (t--) {
187         scanf("%d %d", &n, &m);
188         rep(i, 0, n) {
189             rep(j, 0, m) {
190                 scanf("%d", &M[i][j]);
191                 if (M[i][j] == 2) {
192                     bx = i;
193                     by = j;
194                 } else if (M[i][j] == 3) {
195                     gx = i;
196                     gy = j;
197                     M[i][j] = 0;
198                 } else if (M[i][j] == 4) {
199                     hx = i;
200                     hy = j;
201                     M[i][j] = 0;
202                 }
203             }
204         }
205 
206         solve();
207     }
208 
209     #ifndef ONLINE_JUDGE
210         printf("time = %d.
", (int)clock());
211     #endif
212 
213     return 0;
214 }