追梦算法 | 您所在的位置:网站首页 › 输出一个m行n列的由*组成边框的长方形 › 追梦算法 |
说明
Mitch老鼠在森林里游玩,不小心走进了一个迷宫里面,这个迷宫是一个n行m列的矩阵,迷宫中有些格子是可以走的,有些格子是不能走的,能走的格子用“o”(小写字母o)表示,不能走的格子用“#”表示。 Mitch选择走出迷宫的策略是:先向右,如果右边走不通则选择向下,如果下边走不通则选择向左,如果左边走不通则选择向上;如果四个方向都走不通,则后退选择其他能走的路径。 Mitch从类似下图所示的迷宫的左上角(1,1)点进入迷宫(请注意:入口1,1和出口的n,m点都不是#),请问Mitch有哪些方法可以走出迷宫,走到(n,m)点;请编程求出所有可能的路径,输出这些路径,如果不存在任何的路径可以走出迷宫,请输出“no”。 1 2 3 4 5 1 o o o o o 2 o # # # # 3 o o o o o 4 # o o # o 5 o o o o # 6 o # o o o 输入格式第一行包含两个整数n和m,中间用单个空格隔开,代表迷宫的行和列的数量。 接下来n行,每行m个字符,描述迷宫地图。字符只有“o”或“#”两种,“o”代表这个格子可以走,“#”代表这个格子不能走。(4 3,1->3,2->3,3->4,3->5,3->5,4->6,4->6,5 2:1,1->2,1->3,1->3,2->3,3->4,3->5,3->6,3->6,4->6,5 3:1,1->2,1->3,1->3,2->3,3->4,3->4,2->5,2->5,3->5,4->6,4->6,5 4:1,1->2,1->3,1->3,2->3,3->4,3->4,2->5,2->5,3->6,3->6,4->6,5 5:1,1->2,1->3,1->3,2->4,2->4,3->5,3->5,4->6,4->6,5 6:1,1->2,1->3,1->3,2->4,2->4,3->5,3->6,3->6,4->6,5 7:1,1->2,1->3,1->3,2->4,2->5,2->5,3->5,4->6,4->6,5 8:1,1->2,1->3,1->3,2->4,2->5,2->5,3->6,3->6,4->6,5 dfs模板题 #include #include #include #include #include #include #include #include #include #include using namespace std; int n,m,ans=0,vis[15][15],k; int dx[4]= {0,1,0,-1},dy[4]= {1,0,-1,0}; char a[15][15]; struct ti { int start; int en; }; ti b[100]; void dfs(int x,int y,int step) { step++; b[step].start=x; b[step].en=y; if(x==n&&y==m) { k=1; ans++; cout |
CopyRight 2018-2019 实验室设备网 版权所有 |