多校第10场01,双向bfs

Posted by Cww97 on 2017-08-27

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/77616362
http://blog.csdn.net/cww97/article/details/77616362

双向dfs也可以过,编程复杂度低一些,不过会刚刚好跑复杂度上限,慢了不少

时间差的还挺多的

这里写图片描述
这里写图片描述

dfs的时候剪枝都不能有,会蜜汁wa,丢掉就过了

dfs

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
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long LL;
const int N = 9;
const int dx[] = {-1,-1, 1, 1};
const int dy[] = {-1, 0, 0, 1};
const int MAXSTEP = 10;
int ans;

LL po[9][9];
LL power(int a, int x){
LL ans = 1, tmp = a;
for (; x; x>>=1, tmp *=tmp){if (x&1) ans *= tmp;}
return ans;
}
void InitPower(int a, int b){
for (int i = 1; i <= 6; i++)
for (int j = 1; j <= i; j++)
po[i][j] = power(a, b*i+j);
}

int g[9][9];
struct ha{
int g[N][N], cnt, step;
ha(){}
ha(int a[N][N], int x, int s){
memcpy(g,a,sizeof(g));
cnt = x; step = s;
}
};
map<LL, ha> Hash;
int H = 0, V;
LL hashMove(LL hashNum, int x, int y, int cx, int cy){
return hashNum - (LL)g[x][y] * po[x][y] - (LL)g[cx][cy] * po[cx][cy]
+ (LL)g[x][y] * po[cx][cy] + (LL)g[cx][cy] * po[x][y];
}

void InitDfs(int x, int y, LL hashNum, int step){
if (Hash.find(hashNum) == Hash.end()) Hash[hashNum] = ha(g, ++H, step);
if (step > MAXSTEP) return;
for (int i = 0; i < 4; i++){
int cx = x + dx[i];
int cy = y + dy[i];
if (cx<1 || cx>6 || cy<1 || cy>cx) continue;//outbroad
LL newHash = hashMove(hashNum, x, y, cx, cy);
//if (Hash.find(newHash) != Hash.end()) continue;//visited
swap(g[x][y], g[cx][cy]);
InitDfs(cx, cy, newHash, step + 1);
swap(g[x][y], g[cx][cy]);
}
}

inline void Init(){
InitPower(7, 17);
LL hashNum = 0;
for (int i = 1; i <= 6; i++){
for (int j = 1; j <= i; j++){
g[i][j] = i - 1;
hashNum += g[i][j] * po[i][j];
}
}
Hash.clear();
InitDfs(1, 1, hashNum, 0);
}

void dfs(int x, int y, LL hashNum, int step){
if (Hash.find(hashNum) != Hash.end()){
ans = min(ans, step + Hash[hashNum].step);
}
if (step > MAXSTEP) return;
for (int i = 0; i < 4; i++){
int cx = x + dx[i];
int cy = y + dy[i];
if (cx<1 || cx>6 || cy<1 || cy>cx) continue;//outbroad
LL newHash = hashMove(hashNum, x, y, cx, cy);
swap(g[x][y], g[cx][cy]);
dfs(cx, cy, newHash, step + 1);
swap(g[x][y], g[cx][cy]);
}
}

//inline void bfs(int sx, int sy, )

int main(){
//freopen("in.txt", "r", stdin);
int _, sx, sy;
Init();
for (scanf("%d", &_); _--;){
LL hashNum = 0;
for (int i = 1; i <= 6; i++){
for (int j = 1; j <= i; j++){
scanf("%d", &g[i][j]);
hashNum += g[i][j] * po[i][j];
if (g[i][j] == 0) {sx = i, sy = j;}
}
}
ans = 33; V = 0;
dfs(sx, sy, hashNum, 0);
//bfs(sx, sy, hashNum);
if (ans <= 20) printf("%d\n", ans);
else puts("too difficult");
}
return 0;
}

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
#include <map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long LL;
const int N = 9;
const int dx[] = {-1,-1, 1, 1};
const int dy[] = {-1, 0, 0, 1};
const int MAXSTEP = 10;

LL po[9][9];
LL power(int a, int x){
LL ans = 1, tmp = a;
for (; x; x>>=1, tmp *=tmp){if (x&1) ans *= tmp;}
return ans;
}
void InitPower(int a, int b){
for (int i = 1; i <= 6; i++)
for (int j = 1; j <= i; j++)
po[i][j] = power(a, b*i+j);
}

int g[9][9];
struct ha{
int g[N][N], x, y, step;
LL hashNum;
ha(){}
ha(int a[N][N], int _x, int _y, int s, LL h){
memcpy(g, a, sizeof(g));
x = _x; y = _y;
step = s;
hashNum = h;
}
void print(){
printf("hash: (%d, %d), s = %d, ", x, y, step);
cout << hashNum <<endl;
}
bool operator < (const ha &b) const{
return hashNum < b.hashNum;
}
};
map<LL, ha> Hash;
map<LL, int> vis;
int V;
LL hashMove(LL hashNum, int x, int y, int cx, int cy){
return hashNum - (LL)g[x][y] * po[x][y] - (LL)g[cx][cy] * po[cx][cy]
+ (LL)g[x][y] * po[cx][cy] + (LL)g[cx][cy] * po[x][y];
}

void InitBfs(LL hashNum){
Hash.clear();
queue<ha> Q;
Q.push(ha(g, 1, 1, 0, hashNum));
for (; !Q.empty();){
ha h = Q.front(); Q.pop();
int x = h.x, y = h.y, step = h.step;
if (step > MAXSTEP) return;
hashNum = h.hashNum;
if (Hash.find(hashNum) != Hash.end()) continue;
Hash[hashNum] = ha(g, x, y, step, hashNum);
memcpy(g, h.g, sizeof(g));
for (int i = 0; i < 4; i++){
int cx = x + dx[i];
int cy = y + dy[i];
//printf("(%d, %d) -> (%d, %d)\n", x, y, cx, cy);
if (cx<1 || cx>6 || cy<1 || cy>cx) continue;//outbroad
LL newHash = hashMove(hashNum, x, y, cx, cy);
swap(g[x][y], g[cx][cy]);
Q.push(ha(g, cx, cy, step+1, newHash));
swap(g[x][y], g[cx][cy]);
}
}
}

inline void Init(){
InitPower(7, 17);
LL hashNum = 0;
for (int i = 1; i <= 6; i++){
for (int j = 1; j <= i; j++){
g[i][j] = i - 1;
hashNum += g[i][j] * po[i][j];
}
}
InitBfs(hashNum);
}

int bfs(int sx, int sy, LL hashNum){
//Hash[136260025190489192LL].print();
//cout << hashNum <<endl;
vis.clear();
V = 0;
queue<ha> Q;
for (; !Q.empty();) Q.pop();
Q.push(ha(g, sx, sy, 0, hashNum));
for (; !Q.empty();){
ha h = Q.front(); Q.pop();
int x = h.x, y = h.y, step = h.step;
//if (step <= 5) {ha(g, x, y, step, hashNum).print();}
if (step > MAXSTEP) return 22;
hashNum = h.hashNum;
//h.print();
if (vis.find(hashNum) != vis.end()) continue;
vis[hashNum] = ++V;
if (Hash.find(hashNum) != Hash.end())
return step + Hash[hashNum].step;
memcpy(g, h.g, sizeof(g));
for (int i = 0; i < 4; i++){
int cx = x + dx[i];
int cy = y + dy[i];
//printf("(%d, %d) -> (%d, %d)\n", x, y, cx, cy);
if (cx<1 || cx>6 || cy<1 || cy>cx) continue;//outbroad
LL newHash = hashMove(hashNum, x, y, cx, cy);
swap(g[x][y], g[cx][cy]);
Q.push(ha(g, cx, cy, step+1, newHash));
swap(g[x][y], g[cx][cy]);
}
}
return 22;
}

int main(){
//freopen("in.txt", "r", stdin);
int _, sx, sy;
Init();
for (scanf("%d", &_); _--;){
LL hashNum = 0;
for (int i = 1; i <= 6; i++){
for (int j = 1; j <= i; j++){
scanf("%d", &g[i][j]);
hashNum += g[i][j] * po[i][j];
if (g[i][j] == 0) {sx = i, sy = j;}
}
}
int ans = bfs(sx, sy, hashNum);
if (ans <= 20) printf("%d\n", ans);
else puts("too difficult");
}
return 0;
}