做网站的费用 优帮云,建行信用卡中心官网,南宁seo做法价格,ui设计软件培训学校题目描述
现有一个n∗m大小的迷宫#xff0c;其中1表示不可通过的墙壁#xff0c;0表示平地。每次移动只能向上下左右移动一格#xff08;不允许移动到曾经经过的位置#xff09;#xff0c;且只能移动到平地上。求从迷宫左上角到右下角的所有可行路径的条数。
输入描述…题目描述
现有一个n∗m大小的迷宫其中1表示不可通过的墙壁0表示平地。每次移动只能向上下左右移动一格不允许移动到曾经经过的位置且只能移动到平地上。求从迷宫左上角到右下角的所有可行路径的条数。
输入描述
第一行两个整数n、m2≤n≤5,2≤m≤5分别表示迷宫的行数和列数
接下来n行每行m个整数值为0或1表示迷宫。
输出描述
一个整数表示可行路径的条数。
输入样例
3 3 0 0 0 0 1 0 0 0 0
输出样例
2
代码
#includebits/stdc.h
using namespace std;
int n,m,cnt 0;
int vis[1005][1005],Map[1005][1005];
int dx[4] {0,0,1,-1};
int dy[4] {1,-1,0,0};
bool isValid(int x,int y){return x0xny0ym!vis[x][y]Map[x][y]0;
}
void dfs(int x,int y){if(xn-1ym-1){cnt;return;}vis[x][y] 1;for(int i 0;i4;i){int nextx xdx[i];int nexty ydy[i];if(isValid(nextx,nexty)){dfs(nextx,nexty);}}vis[x][y] 0;
}
int main(){cinnm;for(int i 0;in;i){for(int j 0;jm;j){Map[i][j] 0;}}for(int i 0;in;i){for(int j 0;jm;j){cinMap[i][j];}}dfs(0,0);coutcntendl;}
