DFS算法

DFS是深度优先搜索算法的简称，从它的名字出发：

深度：这个算法可以理解为从树的顶点出发，逐层深入的遍历树的结点，是不断向下的

优先搜索：这个可以理解为我们按照选优条件，去搜索符合条件的情况，符合条件就继续向下搜索，不符合就回溯到初始状态

DFS是通过递归与回溯来实现的，递归需要递归出口，回溯需要判断条件，由此不难得出DFS的大体框架

void dfs(int step)
{
    判断(递归出口)
    选择(选择每一种可能)
    {
        满足选优条件
        {
            标记(递归出口要用)
            下一步dfs(step+1)
        }
        不满足
        {
            回溯到初始状态(这种选择放弃)
            下一种选择
        }
        
        
    }
}

九宫格数独

#include 
#include 
#define r 10
#define c 10
using namespace std;
struct location
{
    int x,y;
};
location point[r*c];
int like[r][c];
int flag;
bool row[r][r];
bool col[c][c];
bool mat[r/3][c/3][r];
int number=0;
int dfs(int n)
{
    if(flag)
        return 0;
    if(n==-1&&flag==0)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                cout<>like[i][j];
            if(like[i][j])
            {
                row[i][like[i][j]]=1;
                col[j][like[i][j]]=1;
                mat[i/3][j/3][like[i][j]]=1;
            }
            else
            {
                point[number].x=i;
                point[number++].y=j;
            }
        }
    dfs(number-1);
    return 0;
}

自动走迷宫

#include 
#include 
using namespace std;
int directionx[5]={0,1,0,-1};
int directiony[5]={1,0,-1,0};
char likemap[50][50];
int sx,sy,ex,ey,nextx,nexty,flag=0;
bool dfs(int x,int y)
{
    likemap[x][y]='*';
    for(int i=0;i<4;i++)
    {
        nextx=x+directionx[i];
        nexty=y+directiony[i];
        if(likemap[nextx][nexty]=='E')
        {
            likemap[nextx][nexty]='*';
            return 1;
        }
        if(likemap[nextx][nexty]==' '&&nextx>=0&&nextx<10&&nexty>=0&&nexty<10)
        {

            flag=dfs(nextx,nexty);
            if(flag)
            break;
        }
    }
    if(flag)
    return 1;
    else
    {
        likemap[x][y]='!';
        return 0;
    }
}
int main()
{
    for(int i=0;i<10;i++)
    {
         for(int j=0;j<10;j++)
    {
        likemap[i][j]=getchar();
        if(likemap[i][j]=='S')
            sx=i,sy=j;
        if(likemap[i][j]=='E')
            ex=i,ey=j;
    }
         getchar();
    }
    dfs(sx,sy);//从起点开始
    for(int i=0;i<10;i++)
    {
        for(int j=0;j<10;j++)
        cout<

#include 
#include 
#define r 8
#define c 8
using namespace std;
int point[r][c];
int flag=1;
int row[r];
int col[c];
int funline(int row,int col)
{
    int i,k;
    for(i=row,k=col;i>=0&&k>=0;i--,k-- )
		if(point[i][k]==1)
            return 0;
	for(i=row,k=col;i>=0&&k<8;i--,k++ )
		if(point[i][k]==1)
			return 0;
    return 1;
}
void dfs(int n)
{
    int i,j;
    if(n>=8)
    {
        cout<<"第"<