NOIP2013 Day2 T3(BFS)

移动初始块必须要在它四周有空白块的存在,如果没有,我们要把空白块移到这些位置。
对于60%数据,直接BFS搜索即可,存储空白块的位置、初始块的位置、移动次数。
对于100%的数据,需要BFS预处理后最短路求解,先坑着有空来写,虽然说如果在考场上我只会打60%╮(╯﹏╰)╭

60%数据解法

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
struct data {
int kx, ky, x, y, step;//空白位置,初始棋位置
};
const int MAXN = 30 + 5;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
int n, m, q, mapi[MAXN][MAXN], vi[MAXN][MAXN][MAXN][MAXN];
int check(int kx, int ky, int x, int y) {
if (!(x>0&&y>0&&kx>0&&ky>0&&x<=n&&y<=m&&kx<=n&&ky<=m)) return false;
if (vi[kx][ky][x][y]||mapi[x][y]==0||mapi[kx][ky]==0) return false;
vi[kx][ky][x][y] = true;
return true;
}
void bfs(int ex, int ey, int sx, int sy,int tx, int ty) {
queue<data> q;
ms(vi, false), ms(vi, 0);
vi[ex][ey][sx][sy] = true, q.push((data){ex, ey, sx, sy, 0});
while (!q.empty()) {
data p = q.front(); q.pop();
for (int i=0;i<4;i++) {
int x = p.x, y = p.y;
int fx = p.kx + dx[i], fy = p.ky + dy[i];
if (fx==x&&fy==y) x = p.kx, y = p.ky;
if (check(fx, fy, x, y)) {
q.push((data){fx,fy,x,y,p.step+1});
if (x==tx&&y==ty) {
printf("%d\n", p.step+1);
return ;
}
}
}
}
printf("-1\n");
}
void clean() {
}
void init() {
clean();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) scanf("%d", &mapi[i][j]);
}
void solve() {
for (int i=1;i<=q;i++) {
int a1, a2, a3, a4, a5, a6;
scanf("%d%d%d%d%d%d", &a1, &a2, &a3, &a4, &a5, &a6);
if (a3==a5&&a4==a6) printf("0\n"); else bfs(a1, a2, a3, a4, a5, a6);
//起点和终点相同特判
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d%d", &n, &m ,&q)==3) init(), solve();
return 0;
}

------ 本文结束 ------