题意:中文...(注意要被推去的位置可以当0走)
解题思路: 状态搜索题 1.对于箱子找目标位置,采用bfs,2.对于人走到推动箱子的位置,采用dfs/bfs;
3.状态的记录,四维hash,记录箱子的位置和人的位置
code:
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cassert> #include <cstring> #include <string> #include <iomanip> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #define LL long long #define inf 0x3f3f3f3f #define eps 1e-9 #define PA system("pause") #define PI acos(-1.0) using namespace std; #define M 10 int mp[M][M], n, m, found; int hash[M][M][M][M], vis[M][M]; int dir[4][2] = {0, -1, 0, 1, 1, 0, -1, 0}; struct node{ int bx, by, mx, my, step; }; bool isok(int x, int y){ return (x >= 0 && x < n && y >= 0 && y < m && mp[x][y] != 1); } void dfs(int sx, int sy, int ex, int ey){ ///搜索人是否能到达推动箱子的位置 if(found)return ; if(sx == ex && sy == ey){ found = 1; return; } for(int i = 0; i < 4; i++){ int tx = sx + dir[i][0]; int ty = sy + dir[i][1]; if(isok(tx, ty) && !vis[tx][ty]){ vis[tx][ty] = 1; dfs(tx, ty, ex, ey); if(found)return; } } } int bfs(int bx, int by, int mx, int my){ ///对箱子进行bfs搜索终点 queue<node>q; node now, tem; memset(hash, 0, sizeof(hash)); now.bx = bx; now.by = by; now.mx = mx; now.my = my; now.step = 0; q.push(now); while(!q.empty()){ now = q.front(); q.pop(); if(mp[now.bx][now.by] == 3) return now.step; for(int i = 0; i < 4; i++){ tem.bx = now.bx + dir[i][0]; tem.by = now.by + dir[i][1]; int tx = now.bx - dir[i][0];///去推动箱子的位置 int ty = now.by - dir[i][1]; if(isok(tem.bx, tem.by) && isok(tx,ty) && !hash[tem.bx][tem.by][tx][ty]){ memset(vis, 0, sizeof(vis)); found = 0; vis[now.bx][now.by] = 1;///不能穿过箱子 vis[now.mx][now.my] = 1; dfs(now.mx, now.my, tx, ty); if(found){ hash[tem.bx][tem.by][tx][ty] = 1; tem.mx = tx; tem.my = ty; tem.step = now.step + 1; q.push(tem); } } } } return -1; } int main() { int t, i, j, bx, by, mx, my; scanf("%d", &t); while(t--){ scanf("%d%d",&n,&m); for(i = 0; i < n; i++){ for(j = 0; j < m; j++){ scanf("%d",&mp[i][j]); if(mp[i][j] == 2){ bx = i; by = j; } if(mp[i][j] == 4){ mx = i; my = j; } } } printf("%d\n", bfs(bx, by, mx, my)); } return 0; }