兰州营销型网站建设,wordpress企业站主题哪个好,公司logo图片,邢台头条新闻最新题面 题目描述 一个迷宫由 R 行 C 列格子组成#xff0c;有的格子里有障碍物#xff0c;不能走#xff1b;有的格子是空地#xff0c;可以走。 给定一个迷宫#xff0c;求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走#xff0c…题面 题目描述 一个迷宫由 R 行 C 列格子组成有的格子里有障碍物不能走有的格子是空地可以走。 给定一个迷宫求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走不能斜着走。 输入 第一行是两个整数R 和 C 代表迷宫的行数和列数。 1≤R,C≤40 ) 接下来是 R 行每行 C 个字符代表整个迷宫。空地格子用 . 表示有障碍物的格子用 # 表示。 迷宫左上角和右下角都是 . 。 输出 输出从左上角走到右下角至少要经过多少步即至少要经过多少个空地格子。 计算步数要包括起点和终点。 样例 输入 5 5
..###
#....
#.#.#
#.#.#
#.#.. 输出 9 链接Link. 最少步数问题可以准备一个步数数组记录从出发点到每个点至少多少步然后不断替换最少步数知道找出最优解。
#include bits/stdc.h
using namespace std;
char a[50][50];
int fx[5] {0 , 0 , 1 , 0 , -1} , fy[5] {0 , 1 , 0 , -1 , 0};
int d[50][50] , n , m;
void dfs( int x , int y , int dep ){d[x][y] dep;int tx , ty;for ( int i 1 ; i 4 ; i ){tx x fx[i];ty y fy[i];if ( a[tx][ty] . dep 1 d[tx][ty] )dfs(tx , ty , dep1);}
}
int main(){scanf(%d%d , n , m);for ( int i 1 ; i n ; i )for ( int j 1 ; j m ; j ){cin a[i][j];d[i][j] INT_MAX; }dfs(1 , 1 , 1);printf(%d , d[n][m]);return 0;
} 这题还有个变种就是给定起点和终点求最少步数要注意第一次到终点不一定是最优解所以要return一下
#include bits/stdc.h
using namespace std;
char a[110][110];
int n , m , s1 ,s2 , e1 , e2 , d[110][110];
int fx[5] {0 , 0 , 1 , 0 , -1},fy[5] {0 , 1 , 0 , -1 , 0};
void dfs(int x , int y , int k){d[x][y] k;if(x e1 y e2){return;}int tx , ty;for( int i 1 ; i 4 ; i ){tx x fx[i];ty y fy[i];if( (a[tx][ty] . || a[tx][ty] T) k 1 d[tx][ty] )dfs(tx , ty , k1);}
}
int main(){scanf(%d%d , n , m);for ( int i 1 ; i n ; i )for ( int j 1 ; j m ; j ){cin a[i][j];if( a[i][j] S ){s1 i;s2 j;}else if(a[i][j] T){e1 i;e2 j;}d[i][j] INT_MAX;}dfs(s1 , s2 , 0);printf(%d , d[e1][e2]);return 0;
}
迷宫的第一条出路 题目描述 已知一 N×N 的迷宫允许往上、下、左、右四个方向行走现请你按照左、上、右、下顺序进行搜索找出第一条从左上角到右下角的路径。 输入 输入数据有若干行第一行有一个自然数 NN≤20表示迷宫的大小 其后有 N 行数据每行有 N 个 0 或 1数字之间没有空格0 表示可以通过1 表示不能通过用以描述迷宫地图。入口在左上角 (1,1)处出口在右下角(N,N) 处。 所有迷宫保证存在从入口到出口的可行路径。 输出 输出数据仅一行为按照要求的搜索顺序找到的从入口到出口的第一条路径搜索顺序左、上、右、下 样例 输入 4
0001
0100
0010
0110 输出 复制(1,1)-(1,2)-(1,3)-(2,3)-(2,4)-(3,4)-(4,4) 链接 将路径的下标K作为递归参数这样递归后退时K也会后退从而覆盖原来的元素
代码
#include bits/stdc.h
using namespace std;
int n , r[410][3];
int fx[5] {0 , 0 , -1 , 0 , 1},fy[5] {0 , -1 , 0 , 1 , 0};
char a[35][35];
void print(int k){for ( int i 1 ; i k ; i ){printf((%d,%d) , r[i][1] , r[i][2]);if( i ! k )printf(-);}
}
void dfs( int x , int y , int k){a[x][y] 1;r[k][1] x;r[k][2] y;if ( x n y n ){print(k);exit(0);}int tx , ty;for ( int i 1 ; i 4 ; i ){tx x fx[i];ty y fy[i];if(a[tx][ty] 0)dfs(tx , ty , k1);}
}
int main(){scanf(%d , n);for ( int i 1 ; i n ; i )for ( int j 1 ; j n ; j )cin a[i][j];dfs(1,1,1);return 0;
}
