预处理 + 图论。

Table of Contents

  1. Description
  2. Solution

其实是个NOIP题，但是感觉一些优化的思路还是挺重要的。

Description

一个$N \times N$的棋盘上有一个空位和一些棋子, 以及一些固定位置, 现在有若干组询问, 给定空位, 起始位置和终止位置, 问最少移动步数.

Solution

我们首先可以暴力地确定$O(n^4)$的状态(空位和当前位置)，然后跑最短路，不过这样实际跑起来太慢了.

注意到一个有效状态只是空位在棋子四周, 否则没有意义, 那我们就可以确定一种新的状态(当前位置和空位所在方向), 那么就只有两种转移, 和空位互换, 以及空位换方向.

空位换方向可以一次预处理.

需要注意的是一开始空位不一定在棋子边上, 可能需要做一次BFS把棋子移过来.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int maxn = 35;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

struct node
{
  int x, y, d;
  node(int _ = 0, int __ = 0, int ___ = 0):
  x(_),y(__),d(___){}
};
int n, m, t;
int mtr[maxn][maxn], f[maxn][maxn][4][4];
int dis[maxn][maxn][4], tmp[maxn][maxn];
int vis[maxn][maxn], v_[maxn][maxn][4];
int ex, ey, sx, sy, tx, ty;
vector<pair<int, int> > v;
queue<node> q;

void bfs(int s1, int s2, int b1, int b2) {
  //printf("%d %d %d %d\n", s1, s2, b1, b2);
  memset(tmp, 0x3f, sizeof tmp);
  tmp[s1][s2] = 0;
  queue< pair<int, int> >q; 
  q.push(make_pair(s1, s2)); vis[s1][s2] = 1;
  while (!q.empty()) {
    pair<int, int> u = q.front(); q.pop();
    int cx = u.first, cy = u.second;
    for (int i = 0; i < 4; ++i) {
      int ix = cx + dx[i], iy = cy + dy[i];
      //if (s1 == ex && s2 == ey) printf("%d %d\n", ix, iy);
      if (ix < 1 || ix > n || iy < 1 || iy > m || !mtr[ix][iy]) continue;
      if (tmp[ix][iy] < 0x3f3f3f3f) continue;
      if (ix == b1 && iy == b2) continue;
      tmp[ix][iy] = tmp[cx][cy] + 1;
      //if(s1 == ex && s2 == ey)printf("%d %d %d\n", ix, iy, tmp[ix][iy]);
      q.push(make_pair(ix, iy));
    }
  }
}
void PreprocessF() {
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) 
      for (int fr = 0; fr < 4; ++fr) {
        int ax = i + dx[fr], ay = j + dy[fr];
        if (ax < 1 || ax > n || ay < 1 || ay > m || !mtr[ax][ay]) continue;
        for (int to = 0; to < 4; ++to) {
          int ix = i + dx[to], iy = j + dy[to];
          if (ix < 1 || ix > n || iy < 1 || iy > m || !mtr[ix][iy]) continue;
          if (fr == to) f[i][j][fr][to] = 0;
          else {
            bfs(ax, ay, i, j);
            f[i][j][fr][to] = tmp[ix][iy];
          }
        }
      }
}
void BeforeSolve() {
  //puts("b");
  bfs(ex, ey, sx, sy);
}
void Spfa() {
  memset(dis, 0x3f, sizeof dis);
  for (int i = 0; i < 4; ++i) {
    int ix = sx + dx[i], iy = sy + dy[i];
    if (ix < 1 || ix > n || iy < 1 || iy > m || !mtr[ix][iy]) continue;
    if (ix == ex && iy == ey) 
      dis[sx][sy][i] = 0, q.push(node(sx, sy, i)), v_[sx][sy][i] = 1;
    else 
      dis[sx][sy][i] = tmp[ix][iy], q.push(node(sx, sy, i)), v_[sx][sy][i] = 1;
    //printf("%d %d %d\n", sx, sy, i);
  }
  while (!q.empty()) {
    node u = q.front(); q.pop();
    v_[u.x][u.y][u.d] = 0;
    //printf("%d %d %d\n", u.x, u.y, u.d);
    //printf("%d\n", dis[u.x][u.y][u.d]);
    //getchar();
    //chg
    int id;
    if (u.d == 1 || u.d == 3) {
      id = ((u.d == 1) ? 3 : 1);
    } else {
      id = ((u.d == 2) ? 0 : 2);
    }
    
    if (dis[u.x + dx[u.d]][u.y + dy[u.d]][id] > 
          dis[u.x][u.y][u.d] + 1) {
        dis[u.x + dx[u.d]][u.y + dy[u.d]][id] = 
        dis[u.x][u.y][u.d] + 1;
        //printf("expand %d %d %d\n", u.x + dx[u.d], u.y + dy[u.d], id);
      if (!v_[u.x + dx[u.d]][u.y + dy[u.d]][id])
        v_[u.x + dx[u.d]][u.y + dy[u.d]][id] = 1, q.push(node(u.x + dx[u.d], u.y + dy[u.d], id));
    }
    for (int i = 0; i < 4; ++i) 
      if (i != u.d) {
        int ix = u.x + dx[i], iy = u.y + dy[i];

        if (ix < 1 || ix > n || iy < 1 || iy > m || !mtr[ix][iy]) continue;
        //printf("%d %d %d\n", u.x, u.y, i);
        //printf("%d %d\n", dis[u.x][u.y][i], dis[u.x][u.y][u.d] + f[u.x][u.y][u.d][i]);
        if (dis[u.x][u.y][i] > dis[u.x][u.y][u.d] + f[u.x][u.y][u.d][i]) {
          dis[u.x][u.y][i] = dis[u.x][u.y][u.d] + f[u.x][u.y][u.d][i];
          if (!v_[u.x][u.y][i])
            v_[u.x][u.y][i] = 1, q.push(node(u.x, u.y, i));//, printf("p %d %d %d\n", u.x, u.y, i);
        }
      }
  }
}

int main() {
  scanf("%d%d%d", &n, &m, &t);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      scanf("%d", &mtr[i][j]);
    }
  }
  PreprocessF();
  while (t--) {
    scanf("%d%d%d%d%d%d",
          &ex, &ey, &sx, &sy, &tx, &ty);
    if (sx == tx && sy == ty) {
      puts("0");
      continue;
    }
    BeforeSolve();
    //puts("bgn");
    Spfa();
    int ans = 0x3f3f3f3f;
    for (int i = 0; i < 4; ++i)
      ans = min(ans, dis[tx][ty][i]);
    if (ans < 0x3f3f3f3f) printf("%d\n", ans);
    else puts("-1");
  }
  return 0;
}