迷宫 加题目 深入搜索

题目:定义一个二维数组: int maze[5][5] = {  0, 1, 0, 0, 0,  0, 1, 0, 1, 0,  0, 0, 0, 0, 0,  0, 1, 1, 1, 0,  0, 0, 0, 1, 0, }; 它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线条数。

代码 #include <iostream>
#include <cstdio>
using namespace std;
bool G[10][10],VIS[10][10];
int d[5]= {-1,0,1,0,-1};
int n,m,nx,ny,ex,ey,CNT;
void dfs(int x,int y) {
 if (x ==ex&&y ==ey) {
  CNT++;
  return;
 }
 for(int k=0; k<4; k++) {
  int l=x+d[k];
  int r=y+d[k+1];
  if (l>=0&&r>=0&&l<=n&&r<=m&&!G [l][r]&&!VIS [l][r]) {       //注意起始位置为(0,0),
   VIS [l][r]=true;
   dfs (l,r);
   VIS [l][r]=false;  //回溯
  }
 }
 return;
}
int main () {
 int t,zx,zy;
 n=4;m=4;
 nx=0;ny=0;ex=4;ey=4;
 G[nx][ny]=0;
 G[0][1]=true;
 G[1][1]=true;
 G[1][3]=true;
 G[3][1]=true;
 G[3][2]=true;
 G[3][3]=true;
 G[4][3]=true;
 dfs (nx,ny);
 cout<<CNT;                 //输出多少路线
 return 0;
}
上一篇:洛谷P1086 花生采摘


下一篇:图论问题复习总结