蓝桥杯-dfs搜索模板题（二）
- P1683 入门
- P1596[USACO10OCT] Lake Counting S
- 1114 棋盘 acwing
- P1025 [NOIP2001 提高组] 数的划分
- P1019 [NOIP2000 提高组] 单词接龙
- 结语
P1683 入门
这道题没有回溯的必要，重复走也不计数。最开始的部分++要补上。
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int n, m;
char g[N][N];
bool st[N][N];
int res = 0;//走过的瓷砖数
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
void dfs(int x, int y)
{
// dfs(x+1,y);
// dfs(x,y+1);
// dfs(x-1;y);
// dfs(x,y-1);
for (int i = 0; i < 4; i++)
{
int a = x + dx[i];
int b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m)continue;
if (g[a][b] != '.')continue;
if (st[a][b])continue;
st[a][b] = true;
res++;
dfs(a, b);
}
}
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i++)
{
scanf("%s", &g[i]);
// for(int j=0;j<m;j++)
// scanf("%c",&g[i][j]);
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (g[i][j] == '@')
{
st[i][j] = true;
dfs(i, j);
}
}
}
res++;
cout << res;
return 0;
}
P1596[USACO10OCT] Lake Counting S
连起来的水坑只算一次
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
char g[N][N];
bool st[N][N];
int res;
int dx[] = { 1,1,1,0,0,-1,-1,-1 };
int dy[] = { -1,0,1,-1,1,-1,0,1 };
void dfs(int x, int y)
{
for (int i = 0; i < 8; i++)
{
int a = x + dx[i];
int b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m)continue;
if (g[a][b] != 'W')continue;
if (st[a][b])continue;
st[a][b] = true;
dfs(a, b);
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
scanf("%s", g[i]);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == 'W' && !st[i][j])
{
st[i][j] = true;
dfs(i, j);
res++;
}
cout << res;
return 0;
}
1114 棋盘 acwing
注意搜索要逐层递推下去，这也是dfs(x + 1, cnt);的作用。
这种情况比如棋子比行数少，前面放完有可能后面就不放了
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, k;
char g[N][N];
bool st[N];
int res = 0;
void dfs(int x, int cnt)
{
if (cnt == k)
{
res++;
return;
}
if (x >= n)return;
for (int i = 0; i < n; i++)
{
if (!st[i] && g[x][i] == '#')
{
st[i] = true;
dfs(x + 1, cnt + 1);
st[i] = false;
}
}
dfs(x + 1, cnt);
}
int main()
{
while (cin >> n >> k, n > 0 && k > 0)
{
for (int i = 0; i < n; i++) scanf("%s", g[i]);
res = 0;
dfs(0, 0);
printf("%d\n", res);
}
return 0;
}
P1025 [NOIP2001 提高组] 数的划分
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int n, k;
int arr[N];
int res = 0;
void dfs(int x, int start, int sum)
{
if (x > k)
{
if (sum == n)
{
res++;
}
return;
}
for (int i = start; sum + i * (k - x + 1) <= n; i++)
{
arr[x] = i;
dfs(x + 1, i, sum + i);
arr[x] = 0;
}
}
int main()
{
cin >> n >> k;
dfs(1, 1, 0);
cout << res;
}
P1019 [NOIP2000 提高组] 单词接龙
细节较多。判断两个字符串是否能接龙，能接龙多少通过k的枚举实现。
并且重叠的部分越短越好，因为整体长度要尽可能长。
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int n;
string words[N];//存单词
int used[N];//记录每个单词的使用次数
int g[N][N];//g[i][j]存第i个单词能否接到第j个单词后面，重合的长度
int res;
void dfs(string dragon, int x)
{
res = max(res, (int)dragon.size());
used[x]++;
for (int i = 0; i < n; i++)
{
if (g[x][i] && used[i] < 2)
{
dfs(dragon + words[i].substr(g[x][i]), i);
}
}
used[x]--;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)cin >> words[i];
char start;
cin >> start;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
string a = words[i], b = words[j];
for (int k = 1; k < min(a.size(), b.size()); k++)
{
if (a.substr(a.size() - k, k) == b.substr(0, k))
{
g[i][j] = k;
break;//尽可能短才可以
}
}
}
for (int i = 0; i < n; i++)
{
if (words[i][0] == start)
{
dfs(words[i], i);//
}
}
cout << res;
}
结语
整理自链接: link
