题面
题目描述
一个迷宫由 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 , dep+1);}
}
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 , k+1);}
}
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 的迷宫，允许往上、下、左、右四个方向行走，现请你按照左、上、右、下顺序进行搜索，找出第一条从左上角到右下角的路径。
输入
输入数据有若干行，第一行有一个自然数 N（N≤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 , k+1);}
}
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;
}
