声明
我的码风可能有点和别人不太一样（其实就是有点奇怪），大家重在意会即可~。
题目
【问题描述】
给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和 终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫 中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。 输入样例 输出样例 【数据规模】 1≤N,M≤5输入输出格式
输入格式：
【输入】
第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点 坐标FX,FY。接下来T行，每行为障碍点的坐标。输出格式：
【输出】
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方 案总数。前言
~~这道题话说是真的水，不过用来练习深搜还是很好的。 ~~这道题十分经典，强烈建议大家自己敲一遍，感受一下这道极其基础的深搜题.
代码详解
为避免繁琐的if语句，先来打个表
const int nextx[4]={0,0,1,-1};const int nexty[4]={-1,1,0,0}; 深搜函数：
void dfs(int x,int y)//深搜 判断边界：if(x<1||y<1||x>n||y>m)//如果越界，则返回 return;
判断是否到达终点：
if(x==fx&&y==fy)//如果到达终点，则方案数加一 { ans++; return;} 搜索与回溯（重点）：
b[x][y]=true;//将当前点标记为已访问 for(int i=0;i<=3;i++) if(b[x+nextx[i]][y+nexty[i]]==false&&a[x+nextx[i]][y+nexty[i]]==true)//如果未访问且不是障碍物 dfs(x+nextx[i],y+nexty[i]); //则继续深搜 b[x][y]=false;//回溯
深搜的完整函数：
void dfs(int x,int y)//深搜 { if(x<1||y<1||x>n||y>m)//如果越界，则返回 return; if(x==fx&&y==fy)//如果到达终点，则方案数加一 { ans++; return; } b[x][y]=true;//将当前点标记为已访问 for(int i=0;i<=3;i++) if(b[x+nextx[i]][y+nexty[i]]==false&&a[x+nextx[i]][y+nexty[i]]==true)//如果未访问且不是障碍物 dfs(x+nextx[i],y+nexty[i]); //则继续深搜 b[x][y]=false;//回溯 } 完整AC代码
你们最爱的AC代码~~~
#includeusing namespace std;bool a[10][10];bool b[10][10]={0};int n,m,t,sx,sy,fx,fy,ans=0;const int nextx[4]={0,0,1,-1};const int nexty[4]={-1,1,0,0}; void dfs(int x,int y)//深搜 { if(x<1||y<1||x>n||y>m)//如果越界，则返回 return; if(x==fx&&y==fy)//如果到达终点，则方案数加一 { ans++; return; } b[x][y]=true;//将当前点标记为已访问 for(int i=0;i<=3;i++) if(b[x+nextx[i]][y+nexty[i]]==false&&a[x+nextx[i]][y+nexty[i]]==true)//如果未访问且不是障碍物 dfs(x+nextx[i],y+nexty[i]); //则继续深搜 b[x][y]=false;//回溯 }int main(){ int tx,ty; cin>>n>>m>>t>>sx>>sy>>fx>>fy; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=true; for(int i=1;i<=t;i++) { cin>>tx>>ty; a[tx][ty]=false; } b[sx][sy]=true; dfs(sx,sy); cout<
后记
这道题由于我手残，敲完代码时不小心关了...关了...于是重打一了遍，浪费了不少时间，不过这些都不重要~ ~ ~各位大佬们看到这里，能否给个赞呢？~>_< ~