DFS_Practice

DFS——exercise.

I learned DFS last month,I almost forgot how to use it,so that I can’t solve a problem in a practice competition. So I require to review it,and review carefully!

Question

在这里你有一个 6*3 的一个数组，每行有1 ， 2 ， 3 三个数，并且每行按照六种顺序分别排列。当每一行都取一个数时，求出6个数之和最大的值。

这里有一个非常笨的方法，就是用六重For循环，是不是很惊讶。没错，当我的小伙伴告诉我时,我的内心是WTF的。

这不是重点，重点是想通过这个简单的题练习一下DFS的思想。

这仅仅是个简单的开始，

Code

#include<iostream>
using namespace std;
int a[10][5];
int res;
void dfs(int x,int sum = 0)
{
    if(x>5)
    {
        //printf("%d",res);
        res = max(res,sum);
        return; 
    }
    dfs(x+1,sum+a[x][0]);
    //dfs(x+1,sum+a[x][1]);
    //dfs(x+1,sum+a[x][2]);
}
int main（）
{
    for(int i=0;i<6;i++)
        for(int j =0;j<3;j++)
            cin>>a[i][j];
    dfs(0);
    cout<<res<<endl;
    return 0;
    }

FIRST

第一次我控制只输入第一列，输出结果为六。

仔细想想，这个跟递归求n的阶乘有异曲同工之妙，不断的调用自己递归，直到满足条件回归。

SECOND

这次我输入了6*2的数据，并将每次的相加求和的结果打印出来，算了算一共64种，也就是说一共有64种组合方法。

THIRD

最后我将所有的数据输入得到了正确的结果18。

LAST

仔细想想还是挺有趣的，想想那个yong FOR循环写的，一共729种可能，想想就可怕. TE,TE,TE,TE…….

DFS模板介绍

DFS问题的解决有一个dfs的套用模板，自我感觉挺有用的，如果你有更好的办法，留评论呦！！！

void dfs(step)`
{
	if(num==end)
	{
        /*do something*/
        return ;}
      /*尝试每一种可能，和遍历数组差不多*/
      for(int i =0;i<end;i++)
      {
			do something;
			dfs(step+1);
			undo something;
			}
rerun 0;
`}

回溯问题

Q

这里拿棋盘问题举个栗子。

POJ1321 请点击这里

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

INPUT

输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

OUTPUT

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

SOLVE

int DFS(int x,int y)
 {
    if(y>=k）
    {
         ans++;
       return 0;
    }
     for(int i=x;i<n;i++)
     {
       for(int j=0;j<n;j++)
        {
            if(!visit[j]&&mp[i][j]=='#')//回溯
             {
                 visit[j]=1;
                 DFS(i+1,y+1);
                visit[j]=0;
            }
        }
     }
     return 0;
 }

在这里menset（visit，0，sizeof（visit））；

DFS过程中，你要退一步，就必然需要保存你走过每个点的所有信息，而在退一步的过程中，你需要从当前状态回到之前的状态，那么这步操作就是回溯，回溯是递归的时候一定会产生的很自然的操作，只不过大部分情况下不需要回溯。