DFS

​ 枚举所有可以到达目标状态的路径，递归或者借助栈来实现,对一个传入状态，遍历它的子状态，对每一个都进行判断，若合法，则递归搜索这一子状态，直到达成目标条件或者状态不合法，则回溯到父亲节点，搜索下一个子状态。

---

递归：

bool judge(参数列表){
    //参数不合法或越界时返回false 否则返回true
}
void dfs(传入状态){
    if(达成目标条件){
        输出信息或者修改信息；
        return;
    }
    for(遍历传入状态的所有子状态){
        if(judge(子状态)){
            传入状态加标记；
            dfs(子状态)；
            传入状态取消标记//回溯
        }
    }
}

洛谷P1605 迷宫

int n,m,t,fx,fy,vis[10][10],arr[10][10],dict[4][2] = {{-1,0},{1,0},{0,-1},{0,1}},ans = 0;
bool judge(int i,int j){
    if(i < 1 || i > n || j < 1 || j > m) return false;//出边界 
    if(arr[i][j] || vis[i][j]) return false;//不合法 障碍 
    return true;
}
void dfs(int i,int j){
    if(i == fx && j == fy){
        ++ans;
        return;
    }
    for(int k=0;k<4;k++){
        int x,y;
        x = i+dict[k][0];
        y = j+dict[k][1];
        if(judge(x,y)){//判断下一个点是否合法 
            ++vis[i][j];//走过的地方加标记 
            dfs(x,y);//继续搜索下一个点 
            --vis[i][j];//回溯取消标记            
        }
    }
}

---

BFS

​ 较DFS高效，找到最快到达目标的一条路径，借助队列实现，状态A的子状态均入队。队列不为空时，弹出队首元素，进行搜索-->队列空；

void judge(node){
    if(非法条件为真 || 范围越界) return false;
    return true;
}
void bfs(A){
    queue<node> q;
    q.push(A);
    while(!q.empty()){
        temp = q.front();
        q.pop();
        if(temp 达成目标条件){
            输出信息；
        }
        if(judge(temp)){//子状态合法则入队
            q.push(temp);
            ++vis[temp];//每个节点只访问一次
        }
    }
}

---

洛谷 P1443 马的遍历

int n,m,sx,sy,map[410][410],dir[2][4] = {{-2,-1,1,2},{-2,-1,1,2}};
bool vis[410][410];
memset(vis,false,sizeof(vis));
memset(map,0xff,sizeof(map));//初始化为-1
struct point{
    int x;
    int y;
}node,top;
//马走日字... 坐标 1 2 或 2 1 变换 
bool judge(int i,int j){
    if(i < 0 || i >= n || j < 0 || j >= m) return false;
    if(vis[i][j]) return false;
    return true;
}
void bfs(int x,int y){
    vis[x][y] = 1;
    map[x][y] = 0;//到初始点需要0步
    queue<point> t;
    node.x = x;
    node.y = y;
    t.push(node);
    while(!t.empty()){
        top = t.front();
        t.pop();
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                if(abs(dir[0][i]) != abs(dir[1][j])){//排除不合法的移动 
                    int _x = top.x + dir[0][i];
                    int _y = top.y + dir[1][j];
                    if(judge(_x,_y)){//判断这一步是否合法 
                        node.x = _x;
                        node.y = _y;
                        t.push(node);
                        vis[_x][_y] = 1;//标记 第一次到达该点的步数一定最优 
                        map[_x][_y] = map[top.x][top.y] + 1;//路径+1                      
                    }
                }
            }
        } 
    } 
}