暑假（补）-5
深度优先搜索（DFS）
DFS全称Deep First Search，是一种遍历或搜索树或图的算法。在解决问题上，利用递归调用自身函数（这种说法好像不正确，领悟思想就好了）来实现搜索的目的。把一个事情拆解成若干个小事，来实现最终的问题。
学好DFS，一定要领悟递归函数之美。下面就直接上题来理解了。
1.放苹果
Description
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
Input
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
Output
对输入的每组数据M和N，用一行输出相应的K。
Sample Input
1
7 3Sample Output
81.有空盘子：举个栗子吧。3个苹果放到5个盘子的方法总数和3个苹果放到3个盘子的方法总数是相等的。
2.没有空盘子：没有空盘子，我们可以看成先给每一个盘子放一个苹果，还剩下m-n个苹果。然后问题就变成了把m-n个苹果放到n个盘子里的问题了，也许有人会问，m-n个苹果放到n个盘子也会出现空盘子的情况啊，不是和前面的有空盘子重复了？的确，会出现空盘子的情况，但是，他们并不是真的空盘子，因为他们最开始已经放了一个，他们在这里的空代表着这个盘子只有最开始放的一个苹果。
因此：
f(m,n)=f(m,n-1)+f(m-n,n) m>=n
f(m,n)=f(m,m) m<n
递归结束条件：结束条件并不是很难发现，当只有一个盘子时明显只有一种方法，另外没有苹果和只有一个苹果的时候也只有一种放法。即f(m,n)=1 n=1,m=0
综上所述：
f(m,n)=1 n=1,m=0
f(m,n)=f(m,m) m<n
f(m,n)=f(m,n-1)+f(m-n,n) m>=n
AC
#include<iostream>
using namespace std;
int dfs(int m,int n)
{
if(n==1||m==0)
return 1;
if(n>m)
return dfs(m,m);
else
return dfs(m,n-1)+dfs(m-n,n);
}
int main()
{
int t;
cin>>t;
while(t--)
{
int m,n;
cin>>m>>n;
cout<<dfs(m,n)<<endl;
}
return 0;
}2.N皇后问题
Problem Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1
8
5
0Sample Output
1
92
10N皇后，比较经典的DFS的题。对每一个位置搜索，并判断位置是否合法，合法则继续向下进行。
因为时间限制，这道题用了打表的方法，记录每种可能下的结果值。具体请看代码。
AC1
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
int ans[20],pos[20];
int num,N;
void dfs(int n)
{
int flag;//判断标志
if(n == N+1)//结束标志
{
num++;
return ;
}
for(int i = 1;i <= N;i++)
{
pos[n] = i;//将第n行第i列的位置下上旗子，保存位置
flag = 1;//此位置以有棋子
/*判断棋子是否合法*/
for(int j =1;j<n;j++)//只需判断已下过棋子的位置
{
if(pos[j] == i || (abs(n-j)) == abs(pos[j] - i))//判断同一列、对角线上是否有
{
flag = 0;
break;
}
}
//合法则继续下一个
if(flag)
dfs(n+1);
}
}
int main()
{
for(N =1;N<=11;N++)
{
num = 0;
dfs(1);
ans[N] = num;//记录结果值
}
int t;
while(cin>>t&&t!=0)
{
cout<<ans[t]<<endl;
}
return 0;
}AC2
这是另外一个，相比于上一个，代码理解起来就容易多了。分为两个函数，一个是dfs函数，另一个是条件判断函数。
#include<stdio.h>
#include<iostream>
using namespace std;
int n,m,ans=0;
int a[20][20],ans[20],o;
int check(int x,int y)
{
for(int i=0;i<x;i++)
if(a[i][y]==1) return 0;
for(int i=x-1,j=y-1;i>=0&&j>=0;i--,j--)
if(a[i][j]==1) return 0;
for(int i=x-1,j=y+1;i>=0&&j<o;i--,j++)
if(a[i][j]==1) return 0;
return 1;
}
void dfs(int x)
{
if(x==o)
{
ans[o]++;
return;
}
for(int i=0;i<o;i++)
{
if(check(x,i))
{
a[x][i]=1;
dfs(x+1);
a[x][i]=0;
}
}
}
int main()
{
for(o=1;o<=10;o++)
{
dfs(0);
}
while(cin>>n&&n!=0)
{
cout<<ans[n]<<endl;
}
return 0;
}3.红与黑
Problem Description
There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.
Write a program to count the number of black tiles which he can reach by repeating the moves described above.
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.
There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.
‘.’ - a black tile ‘#’ - a red tile ‘@’ - a man on a black tile(appears exactly once in a data set)
Output
For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).
Sample Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0Sample Output
45
59
6
13这是一个搜图的问题，用DFS，恰到好处，只需判断是否满足条件就可以ans++，比较简单的一道，要注意输入哦（因为这wa了好久）
AC
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
char a[25][25];
int vis[25][25];
int w[4][2]={1,0,-1,0,0,1,0,-1};
int x,y,xx,yy,xx1,yy1;
int ans;
void dfs(int x,int y)
{
vis[x][y] = 1;
if(x<0||y<0||x>=xx||y>=yy)
return ;
for(int i =0;i<4;i++)
{
int dx = x+w[i][0];
int dy = y+w[i][1];
if(dx>=0&&dy>=0&&dx<xx&&dy<yy&&a[dx][dy]!='#'&&vis[dx][dy]==0)
{
ans++;
dfs(dx,dy);
}
}
}
int main()
{
while(~scanf("%d %d",&yy,&xx)&&xx&&yy)
{
memset(vis,0,sizeof(vis));
ans = 1;
for(int i =0;i<xx;i++)
{
for(int j =0;j<yy;j++)
{
cin>>a[i][j];
if(a[i][j]=='@')
{
xx1 = i;
yy1 = j;
}
}
}
dfs(xx1,yy1);
cout<<ans<<endl;
}
return 0;
}腾讯云开发者
