一.P1683 入门
算法思想：设置瓷砖状态st，这里瓷砖状态是否走过决定计数与否，因为可以重复走过但只记一次，所以可以不用回溯。每一次dfs都记录此时的坐标与进入可能的新坐标。
const int N = 25;
int W, H;
char map[N][N];//存地图
bool st[N][N];//存每个瓷砖走过状态
int res;//记录走过的瓷砖数
//记录4个方向
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
//当前访问到的坐标是(x,y)
void dfs(int x, int y)
{
//模拟走迷宫
for (int i = 0; i < 4; i++)
{
int a = x + dx[i], b = y + dy[i];//新坐标
if (a < 0 || a >= H || b < 0 || b >= W) continue;//是否超出边界
if (map[a][b] != '.') continue;//是否为坏瓷砖
if (st[a][b]) continue; //是否已经走过这块瓷砖
st[a][b] = true;//设置已走瓷砖的状态
res++;
dfs(a, b);
/*这里可以重复走瓷砖但不多次计数，无需回溯*/
}
}
int main()
{
scanf("%d %d", &W, &H);
for (int i = 0; i < H; i++)
scanf("%s", map[i]);
for (int x = 0; x < H; x++)
{
for (int y = 0; y < W; y++)
{
if (map[x][y] == '@')
{
st[x][y] = true;
dfs(x, y);//进入第一块砖
}
}
}
res++;
printf("%d", res);
return 0;
}二.P1596 [USACO10OCT] Lake Counting S
类似上题，记录水格状态即可。
#include<iostream>
#include<stdio.h>
using namespace std;
int N, M;//N行M列
char map[105][105];//存地图
bool st[105][105];//存水的状态（是否已经联通其他已经计数的水坑）
int dx[10] = { 1,1,1,0,0,-1,-1,-1 };
int dy[10] = { 1,0,-1,1,-1,1,0,-1 };
int res;//存水坑数
//(x,y)当前判断的坐标
void dfs(int x, int y)
{
for (int i = 0; i < 8; i++)
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= N || b < 0 || b >= M) continue;
if (map[a][b] != 'W') continue;
if (st[a][b]) continue;
st[a][b] = true;
dfs(a, b);
}
}
int main()
{
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++)
scanf("%s", map[i]);
for (int x = 0; x < N; x++)
{
for (int y = 0; y < M; y++)
{
if (map[x][y] == 'W' && st[x][y] == false)
{
//st[x][y] = true;//设置状态
res++;
dfs(x, y);
}
}
}
printf("%d", res);
return 0;
}三.1114. 棋盘问题
算法思想：dfs按列扫描，在每一列具体扫描中向下扫描行，设置行的状态，当某一行已经放过棋子，跳过此行，继续扫描下一行，直到找到没有放过棋子的一行，就将此行状态设置为真。然后去扫描下一列。
ps:注意一列不放棋子的情况
const int N = 10; // n 最大是 8，多开到 10
int n, k; // n * n 棋盘，要放 k 个棋子
char g[N][N]; // 存地图
int res; // 存答案
bool row[N]; // bool 数组存每一行是否放过棋子
int cnt; // 存目前放了多少个棋子
//现在放第x列（按列扫描）
void dfs(int x)
{
if (cnt == k) // 如果已经放完 k 个棋子
{
res++; // 答案加一
return; // 不用在执行下面的操作，直接 return
}
if (x > n) return; // 判断边界，如果超出棋盘范围，则之前的搜索方案不合法，直接 return
for (int i = 1; i <= n; i++) // 枚举棋子放在第几行
{
if (g[i][x] == '#' && !row[i]) // 如果该位置属于棋盘范围且这行之前没有放过棋子
{
cnt++; // 多放一个，cnt 加一
row[i] = true; // 标记这一行，之后不能放
dfs(x + 1); // dfs 下一列
cnt--; // 回溯，拿掉这颗棋
row[i] = false; // 回溯，这一行又能放了
}
}
dfs(x + 1); // 还要在进行 dfs 是因为 k <= n，有可能不是每列都放了棋子，这里的 dfs 搜索这一列不放棋子的情况
}
int main()
{
while (scanf("%d%d", &n, &k)) // 多组数据
{
if (n == -1 && k == -1) break; // 输入结束，跳出循环
for (int i = 1; i <= n; i++)
{
getchar(); // 因为 scanf 输入会读到换行，所以要用 getchar 先把换行读完
for (int j = 1; j <= n; j++) scanf("%c", &g[i][j]); // 输入地图不多说
}
res = cnt = 0; // 初始化
memset(row, 0, sizeof row); // 初始化
dfs(1); // 执行 dfs
printf("%d\n", res); // 输出答案不多说
}
return 0;
}
四.P1025 [NOIP2001 提高组] 数的划分
算法思想：组合型枚举，带一个start变量保证以后的不小于start即可，在带一个即时记录所用数字和变量判断剪枝。
#include<iostream>
using namespace std;
const int N = 10;
int arr[N];//存临时分组
int n,k;
int res;//存结果
//枚举到第x份，这一份至少要大于等于start,now_sum为前面的份总和
void dfs(int x,int start,int now_sum)
{
if (now_sum>n) return;
if (x > k)
{
if (now_sum == n)
{
res++;
}
return;
}
for (int i = start; i<n; i++)
{
if (n - now_sum < i) break;
arr[x] = i;
dfs(x + 1,i,now_sum+i);
arr[x] = 0;//恢复现场
}
}
int main()
{
cin>>n>>k;
dfs(1,1,0);
cout << res;
return 0;
}
