#4132. 深搜最短路径模版
深搜最短路径模版
#include using namespace std; int map1[21][21]; //记录地图 bool vis[21][21]; //记录某一个位置是否走过 int xx[] = {-1,1,0,0}; //x方向偏移量,上下 int yy[] = {0,0,-1,1}; //y方向偏移量,左右 int n,m,ans; // 深度优先搜索 void dfs({{ select(1) }} /* 当前搜索点的横纵坐标 */){ // 到达终点 if({{ input(2) }} && {{ input(3) }}){ ans++; return; } for(int i = 0; i < 4; i++){ int nx = {{ input(4) }}; int ny = {{ input(5) }}; if(nx < 1 || ny < 1 || nx > n || ny > m) continue; if({{ input(6) }} == true) continue; // 已走过 if({{ input(7) }} == 1) continue; // 是障碍 vis[nx][ny] = true; dfs({{ input(8) }}); // 递归向下搜索 {{ input(9) }}; // 回溯:取消标记 } } int main(){ cin >> {{ input(10) }} >> m; // 读入行列 for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> map1[i][j]; } } if(map1[1][1] == 2){ cout << 0; }else{ vis[1][1] = true; dfs(1,1); cout << ans << endl; } return 0; }