深度优先搜索的特色

递归：判断有解还是无解

1. 返回值设计
   1. 如果只是遍历，返回值void即可
   2. 判断是否有路径，返回值bool
2. 参数设计：DFS(当前结点信息，终点状态)
3. 去重，visited集合
4. 记录路径：栈

bool DFS(current,end){
	stack.push(current);
	visited[current]=true;
	if(current == end){
		return true;
	}
	while(current有未被访问的邻居){
		if(DFS(该邻居,end) == true&&visited[邻居]=false){
			return true;
		}
	}
	visited[current]=false;
	stack.pop();
	return false;
}

例题——A knight’s journey

代码

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
//#include <bits/stdc++.h>
using namespace std;
int direction[8][2]={
        {-1,-2},{1,-2},
        {-2,-1},{2,-1},
        {-2,1},{2,1},
        {-1,2},{1,2}
};
bool visited[50][50]= {false};
bool DFS(int x, int y, int current, int p, int q, string path){
    //把本结点加入路径
    path += (y+'A');
    path += (x+'1');
    //本节点设为已经访问
    visited[x][y]= true;
    //判断是否达到终点
    if (current==p*q){
        printf("%s\n\n",path.c_str());
        return true;
    }

    //遍历邻居
    for (int i = 0; i < 8; ++i) {
        if (x+direction[i][0] >= 0 &&x+direction[i][0]<p&&
            y+direction[i][1] >= 0 &&y+direction[i][1]<q&&
        visited[x+direction[i][0]][y+direction[i][1]]== false){
            if (DFS(x+direction[i][0],y+direction[i][1],current+1,p,q,path)==true){
                //如果下一个结点能够达到，就说明本节点也能达到
                return true;
            }

        }

    }
    //不存在从本节点除法到终点的路径
    visited[x][y]= false;
    path.substr(0,path.size()-2);//删掉最后两个字符
    return false;
}

int main() {
    int n,p,q;
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d",&p,&q);
        string path;
        printf("Scenario #%d:\n",i+1);
        for (int j = 0; j < p; ++j) {
            for (int k = 0; k < q; ++k) {
                visited[j][k]= false;
            }
        }
        if (DFS(0,0,1,p,q,path)== false){
            printf("impossible\n\n");
        }
    }
    return 0;
}

例题——Square

代码

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
//#include <bits/stdc++.h>
using namespace std;
int m;
int stick[30];
bool is_used[30];
bool DFS(int current_side, int current_length,int position, int side){
    //current_side  已经拼好的边长个数
    //current_length正在拼的边长的长度
    //position      木棍遍历的起点
    if (current_side==3){
        return true;
    }
    for (int i = position; i < m; ++i) {
        if (is_used[i]==true||current_length+stick[i]>side){
            continue;
        }
        //暂时拿这个木棍拼边
        is_used[i]= true;
        if (current_length+stick[i]<side){
            if (DFS(current_side,current_length+stick[i],i+1,side)==true){
                return true;
            }
        } else if(current_length+stick[i]==side){
            if (DFS(current_side+1,0,0,side)== true){
                return true;
            }
        }
        //取回刚刚的木棍
        is_used[i]= false;
    }
    return false;
}

int main() {
    int n;
    scanf("%d",&n);
    for (int idx = 0; idx < n; ++idx) {
        scanf("%d",&m);
        int total = 0;
        for (int i = 0; i < m; ++i) {
            scanf("%d",&stick[i]);
            total += stick[i];
            is_used[i]= false;
        }
        if (total%4==0&& DFS(0,0,0,total/4)){
            printf("yes\n");
        } else{
            printf("no\n");
        }
    }
    return 0;
}