经典的方块游戏

1 * 2 * 1的砖块 最少步数到达一个指定的洞中

很明显的bfs，状态表示时用一个p值0，1， 2分别表示砖块立起来，横躺着和竖躺着，判重时用一个三维数组即可 vis [p状态] [行位置] [列位置]

那么每次直接从一个状态转移到另一种状态，坐标位置同时改变即可

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            using namespace std; //LOOP #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) //OTHER #define PB push_back //INPUT #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RS(s) scanf("%s", s) typedef long long LL; typedef unsigned long long ULL; typedef vector 
           
             VI; const double eps = 1e-9; const int MOD = 1000000007; const double PI = acos(-1.0); const int INF = 0x3f3f3f3f; const int maxn = 110; int n, m; char s[510][510]; int d[510][510][3]; bool vis[510][510][3]; int dir[][4][3] = {{{-2, 0, 2}, {0, 1, 1}, {1, 0, 2}, {0, -2, 1}}, {{-1, 0, 0}, {0, 2, -1}, {1, 0, 0}, {0, -1, -1}}, {{-1, 0, -2}, {0, 1, 0}, {2, 0, -2}, {0, -1, 0}} }; struct Node{ int x, y; int p; Node(){} Node(int x, int y, int p): x(x), y(y), p(p){} bool operator == (const Node& a) const { return x == a.x && y == a.y && p == a.p; } }st, ed, now, nxt; inline void getorder(int &x1, int &y1, int &x2, int &y2, int &p) { if (x1 > x2 || (x1 == x2 && y1 > y2)) { swap(x1, x2); swap(y1, y2); } if (x1 == x2) p = 1; else p = 2; if (x1 == x2 && y1 == y2) p = 0; } vector
            
              > stv; bool ok(int x, int y, int p) { if (x < 0 || x >= n || y >= m || y < 0) return 0; if (p == 0) { if (s[x][y] == '#' || s[x][y] == 'E') return 0; return 1; } if (s[x][y] == '#') return 0; int x2, y2; if (p == 1) x2 = x, y2 = y + 1; if (p == 2) x2 = x + 1, y2 = y; if (x2 < 0 || x2 >= n || y2 >= m || y2 < 0) return 0; if (s[x2][y2] == '#') return 0; return 1; } int bfs() { if (st == ed) return 0; queue
             
              q; int x, y, p; CLR(vis, 0); d[st.x][st.y][st.p] = 0; vis[st.x][st.y][st.p] = 1; q.push(st); while (!q.empty()) { now = q.front(); q.pop(); REP(i, 4) { x = now.x + dir[now.p][i][0]; y = now.y + dir[now.p][i][1]; p = now.p + dir[now.p][i][2]; if (!ok(x, y, p) || vis[x][y][p]) continue; nxt.x = x, nxt.y = y, nxt.p = p; if (nxt == ed) return d[now.x][now.y][now.p] + 1; d[x][y][p] = d[now.x][now.y][now.p] + 1; vis[x][y][p] = 1; q.push(nxt); } } return -1; } int main() { //freopen("0.txt", "r", stdin); while (~RII(n, m) && n + m) { stv.clear(); REP(i, n) { RS(s[i]); REP(j, m) { if (s[i][j] == 'X') { s[i][j] = '.'; stv.push_back(make_pair(i, j)); } if (s[i][j] == 'O') { s[i][j] = '.'; ed.x = i; ed.y = j; ed.p = 0; } } } int pp = 0; if (stv.size() == 2) getorder(stv[0].first, stv[0].second, stv[1].first, stv[1].second, pp); st.x = stv[0].first; st.y = stv[0].second; st.p = pp; int ans = bfs(); if (ans == -1) puts("Impossible"); else printf("%d\n", ans); } return 0; }