题目描述

n*n大小的迷宫棋盘，从(1,1)到(n,n)共有多少条路径

多少条对应DFS
最短对应BFS

DFS模板

bool st[N][N]; //状态数组（用于标记）

void dfs(int u){
    //结束时情况

    //遍历每一种可能
        //判断不合法情况

        //合法情况，走向下一步，进行标记
        //dfs(u+1)
        //回溯（回复现场）

}

C++ 代码

#include <iostream>

using namespace std;

bool st[10][10];  //存储状态
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};  //方向
int ans,n;

void dfs(int x,int y){
    //判断结束情况
    if(x==n&&y==n){
        ans++;
        return;
    }


    //遍历每一种可能
    for(int i=0;i<4;i++){
        int ix=x+dx[i];
        int iy=y+dy[i];

        //判断不合法情况
        if(ix<1||iy<1||st[ix][iy]||ix>n||iy>n) continue;

        //走到下一步，标记
        st[ix][iy]=true;
        dfs(ix,iy);

        //回溯（恢复现场）
        st[ix][iy]=false;

    }

}


int main(){
    cin>>n;
    st[1][1]=true;  //起点标记
    dfs(1,1);
    cout<<ans;


    return 0;
}