kuangbin专题2--搜索进阶

进阶搜索题目

A

一个bfs,要求输出移动的步骤。
然而写完之后T了emmmmm

Tle的代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4;
int mp[maxn][maxn];
int fact[10];
void init(){
fact[0] = 1;
for(int i=1; i<9; i++) fact[i] = fact[i-1]*(i);
return;
}
int n;
int sx, sy;
struct Node{
int m[maxn][maxn];
int step = 0;
int x, y;
char mov[140];
int len;
};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
char move_di[4] ={'u', 'd', 'r', 'l'};
const int max_num = 362879+10;
int ter = 0;
int vis[max_num];
int cal(int num[][maxn]){
int temp[9];
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) temp[i*3+j] = num[i][j];
int ans = 0;
for(int i=0; i<9; i++){
int cnt = 0;
for(int j=i+1; j<9; j++){
if(temp[j]<temp[i]){
cnt++;
}
}
ans += fact[8-i]*cnt;
}
return ans;
}
bool judge(int x, int y){
if(x<0||x>=3||y<0||y>=3) return false;
return true;
}
char last_ans[140];
bool bfs()
{
Node s;
s.x = sx;
s.y = sy;
s.step = 0;
s.len = 0;
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) s.m[i][j] = mp[i][j];
queue<Node> q;
q.push(s);
int number = cal(s.m);
//cout<<number<<endl;
vis[number] = true;
while(!q.empty()){
Node temp = q.front();
q.pop();
number = cal(temp.m);
if(number == ter) {
temp.mov[temp.len] = '\0';
for(int i=0; i<=temp.len; i++){
last_ans[i] = temp.mov[i];
}
return true;
}
for(int i=0; i<4; i++){
int nx = temp.x+dx[i];
int ny = temp.y+dy[i];
if(judge(nx, ny)){
Node temp1 = temp;
swap(temp1.m[temp.x][temp.y], temp1.m[nx][ny]);
number = cal(temp1.m);
if(vis[number])continue;
else{
temp1.mov[temp1.len] = move_di[i];
temp1.len = temp.len+1;
temp1.step = temp.step+1;
temp1.x = nx;
temp1.y = ny;
vis[number] = true;
q.push(temp1);
}
}
}
}
return false;
}
int main()
{
init();
ios::sync_with_stdio(false);
int tot = 0;
char temp[30];
while(gets(temp)){
tot = 0;
memset(vis, 0, sizeof(vis));
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
char temp_num;
temp_num = temp[tot];
tot += 3;
if(temp_num == 'x') mp[i][j] = 0;
else mp[i][j] = temp_num-'0';
if(mp[i][j] == 0){
sx = i, sy = j;
}
}
}
bool is_true;
is_true = bfs();
if(!is_true){
printf("unsolvable\n");
}
else cout<<last_ans<<endl;
}
return 0;
}

未解决的问题

文章目录
  1. 1. A
    1. 1.1. Tle的代码
  2. 2. 未解决的问题
{{ live2d() }}