2019.8.30做的三道题
Mayan游戏
没啥好说的，看着就恶心，还好有大佬的题解指导要不然我就废废废了
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdlib>
const int maxn=10;
using namespace std;
int read()
{
int X=0,w=0; char ch=0;
while(!isdigit(ch))
{
w|=ch=='-';ch=getchar();
}
while(isdigit(ch))
X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
int n,map[maxn][maxn],ans[maxn][5],last[maxn][maxn][maxn],xiao[maxn][maxn];
bool remove()
{
int flag=0;
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
{
if(i-1>=1&&i+1<=5&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j]&&map[i][j])
{
xiao[i-1][j]=1;
xiao[i+1][j]=1;
xiao[i][j]=1;
flag=1;
}
if(j-1>=1&&j+1<=7&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1]&&map[i][j])
{
xiao[i][j]=1;
xiao[i][j+1]=1;
xiao[i][j-1]=1;
flag=1;
}
}
if(!flag)
return 0;
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
if(xiao[i][j])
{
xiao[i][j]=0;
map[i][j]=0;
}
return 1;
}
bool check()
{
for(int i=1;i<=5;i++)
if(map[i][1])
return 0;
return 1;
}
void copy(int x)
{
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
last[x][i][j]=map[i][j];
}
void update()
{
for(int i=1;i<=5;i++)
{
int wow=0;
for(int j=1;j<=7;j++)
{
if(!map[i][j])
wow++;
else
{
if(!wow)
continue;
map[i][j-wow]=map[i][j];
map[i][j]=0;
}
}
}
}
void move(int i,int j,int x)
{
int tmp=map[i][j];
map[i][j]=map[i+x][j];
map[i+x][j]=tmp;
update();
while(remove())
update();
}
void dfs(int x)
{
if(check())
{
for(int i=1;i<=n;i++)
{
if(i!=1)printf("\n");
for(int j=1;j<=3;j++)
printf("%d ",ans[i][j]);
}
exit(0);
}
if(x==n+1)
return;
copy(x);
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
{
if(map[i][j])
{
if(i+1<=5&&map[i][j]!=map[i+1][j])
{
move(i,j,1);
ans[x][1]=i-1;
ans[x][2]=j-1;
ans[x][3]=1;
dfs(x+1);
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
map[i][j]=last[x][i][j];
ans[x][1]=-1;
ans[x][2]=-1;
ans[x][3]=-1;
}
if(i-1>=1&&map[i-1][j]==0)
{
move(i,j,-1);
ans[x][1]=i-1;
ans[x][2]=j-1;
ans[x][3]=-1;
dfs(x+1);
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
map[i][j]=last[x][i][j];
ans[x][1]=-1;
ans[x][2]=-1;
ans[x][3]=-1;
}
}
}
}
int main()
{
n=read();
for(int i=1;i<=5;i++)
{
for(int j=1;j<=8;j++)
{
int x=read();
if(x==0)
break;
map[i][j]=x;
}
}
memset(ans,-1,sizeof(ans));
dfs(1);
puts("-1");
return 0;
}
|
n皇后问题
经典的一道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
| #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=20;
int n;
char ans[maxn][maxn];
bool h[maxn],dj[maxn],fdj[maxn];
void init()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
ans[i][j]='.';
}
}
void dfs(int u)
{
if(u==n)
{
for(int i=0;i<n;i++)
cout<<ans[i]<<endl;
cout<<endl;
return ;
}
for(int i=0;i<n;i++)
{
if(!h[i]&&!dj[u+i]&&!fdj[n-u+i])
{
ans[u][i]='Q';
h[i]=dj[u+i]=fdj[n-u+i]=true;
dfs(u+1);
h[i]=dj[u+i]=fdj[n-u+i]=false;
ans[u][i]='.';
}
}
}
int main()
{
cin>>n;
init();
dfs(0);
return 0;
}
|
导弹防御系统
刷新了我的三观，可能是因为我太菜了？？
多亏了yxc大佬
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=50;
int n;
int h[maxn];
int up[maxn],down[maxn];
bool dfs(int u,int su,int sd,int depth)
{
if(su+sd>depth)
return false;
if(u==n)
return true;
bool flag=true;
for(int i=1;i<=su;i++)
{
if(up[i]<h[u])
{
int t=up[i];
up[i]=h[u];
if(dfs(u+1,su,sd,depth))
return true;
up[i]=t;
flag=false;
break;
}
}
if(flag)
{
up[su+1]=h[u];
if(dfs(u+1,su+1,sd,depth))
return true;
}
flag=true;
for(int i=1;i<=sd;i++)
{
if(down[i]>h[u])
{
int t=down[i];
down[i]=h[u];
if(dfs(u+1,su,sd,depth))
return true;
down[i]=t;
flag=false;
break;
}
}
if(flag)
{
down[sd+1]=h[u];
if(dfs(u+1,su,sd+1,depth))
return true;
}
return false;
}
int main()
{
while(cin>>n&&n)
{
for(int i=0;i<n;i++)
cin>>h[i];
int depth=0;
while(!dfs(0,0,0,depth))
depth++;
cout<<depth<<endl;
}
return 0;
}
|
总结
这三道题都是比较经典的搜索题，我现在目前在死磕搜索、，一定要弄懂，弄会，弄明白，这样才能从量变走向质变（我才不要变质）
