dfs板子
bool check(参数) {
if(满足条件)
return ture;
return false;
}
void dfs(int step) {
if(到达边界){
输出或其他相关操作 //根据题意添加
return ;
}
if(越界 / 不合法的状态)
return;
for() {
if(满足check) {
修改操作; //根据题意判断是否执行该操作 **1**
标记;
dfs(step + 1);//继续下一步
(还原标记) //根据题意判断是否执行该操作 **2**
//如果加上（还原标记）就是 回溯法
}
}
}
例题1 选数
题目描述
已知 n 个整数 x_1,x_2,x_n，以及1个整数k(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3，4个整数分别为3,7,12,193,7,12,19时，可得全部的组合与它们的和为：
3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3+7+19=293+7+19=29。
输入输出样例
输入
4 3
3 7 12 19
输出
1
#include<iostream>
#include<cstring>
int a[22], p[22];
bool vis[22];
int n, k,sum,ans;
using namespace std;
bool isprime(int n) { //判断素数
if(n <= 1) return false;
for(int i = 2; i * i <= n; ++i)
if(n % i == 0)
return false;
return true;
}
void dfs(int step){
if(step == k + 1){
if(isprime(sum))
ans++;
return ;//返回之前的一步（最近一次调用dfs函数的地方）
}
for(int i = 1; i <= n; ++i) {
if(vis[i] == false && i > p[step - 1]) {
p[step] = i;
sum += a[i];
dfs(step + 1);
vis[i] = false;
sum -= a[i];
}
}
}
int main() {
memset(vis,0,sizeof(vis));//初始化
cin>>n>>k;
for(int i = 1; i <= n; ++i) {
cin>>a[i];
p[i] = i;
}
ans = 0;
dfs(1);
cout<<ans<<endl;
return 0;
}
例题2 迷宫
题目背景
给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
题目描述
无
输入格式
第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点坐标FX,FY。接下来T行，每行为障碍点的坐标。
输出格式
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。
输入输出样例
输入
2 2 1
1 1 2 2
1 2
输出
1
说明/提示
【数据规模】
1≤N,M≤5
PS:把图画出来推导更方便,也可以用广搜来做
#include<iostream>
int a[6][6], book[6][6];
int n, m, t, p, q, sum;
using namespace std;
void dfs(int x, int y, int step) {
int next[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
int tx, ty;
if(x == p && y == q) { //判断是否到达终点
sum++; //到达终点，方案数加一
return ;
}
for(int i = 0; i < 3; ++i){
tx = x + next[i][0];
ty = y + next[i][1];//计算下一个点的坐标
if(tx < 1 || tx > n || ty < 1 || ty > m) continue; //判断是否越界
if(a[tx][ty] == 0 && book[tx][ty] == 0) {
book[tx][ty] = 1; //标记
dfs(tx, ty, step); //尝试下一个点
book[tx][ty] = 0;//取消标记
}
}
return;
}
int main(void){
int sx, sy, fx, fy;
cin>>n>>m>>t;
cin>>sx>>sy>>p>>q;
book[sx][sy] = 1; //标记该点已走，防止重复走
for(int i = 1; i <= t; ++i){
cin>>fx>>fy;
a[fx][fy] = 1; //障碍物的初始化
}
dfs(sx, sy, 0);// 参数一起点横坐标。二 起点纵坐标，三 初始化步数为0
cout<<sum<<endl;
return 0;
}
例题3 油田
题意翻译
【题目大意】输入多个m行n列的矩阵，用00表示输入结束。找出有多少块石油区域，用“@”代表石油，假如两个“@”在横，竖或对角线上相邻，就说它们位于同一区域，对于每个输入，输出一个数表示有几个石油区域。
感谢@songhn 提供的翻译
输入输出样例
输入 #1复制
1 1
3 5
#@#@#
##@##
#@#@#
1 8
@@####@#
5 5
####@
#@@#@
#@##@
@@@#@
@@##@
0 0
输出 #1复制
0
1
2
2
PS由于博客格式限制，这里改了样例的输入符号
点此进入原题
#include<iostream>
#include<cstring>
char a[103][103];
int n ,m;
using namespace std;
bool check(int x, int y) {
if(x >= 0 && x <= m && y >= 0 && a[x][y] == '@') //判断是否是油田
return 1;
return 0;
}
int dfs(int x, int y){
int next[8][2] = {{1, 0},{0,1},{-1,0},{0,-1},{1,-1},{-1,1},{-1,-1},{1,1}};
int tx, ty;
if(check(x, y)) {
a[x][y] = '.';
for(int i = 0; i < 8; ++i) {
tx = x + next[i][0];
ty = y + next[i][1];
dfs(tx, ty);
}
return 1;
}
return 0;
}
int main() {
while(cin>>m>>n && (m != 0 && n != 0)) { // 简单粗暴地判断终止输入的条件
int sum = 0; //切记在循环内部初始化
memset(a, 0, sizeof(a));
for(int i = 0; i < m; ++i){
cin>>a[i];
}
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(dfs(i, j)) sum++;//发现油田
}
}
cout<<sum<<endl;
}
return 0;
}
感谢前辈