5
迷宫
分析：本道题考察搜索算法，主要方法：地图中的每个点都做上标记，如果没有走过，则标记为0，如果走过了则标记为1，从起点开始，上下左右进行搜索，判断下一个点是否能走并且是否有星星，如果能走则接着搜索下一个点进行判断，如果是星星则将统计变量加1，并将该点设置成’.’。其中一定要注意某个点能走的条件。输入地图，在输入的过程中如果遇到‘S’，代表初始位置，将其坐标记录下来，作为搜索的起点。并将该点标记为1，开始以起点坐标进行深度搜索。代码如下：
#include <iostream>
using namespace std;
char map[202][202];
int n,m,s,visit[202][202],cnt,sx,sy;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void dfs(int x,int y){
//如果是‘*’，则将统计变量加1，并将该点设置为‘.’
if(map[x][y]==‘*’){
cnt++;
map[x][y]=‘.’;
}
//开始进行上下左右搜索
for(int i =0; i <4; i++){
int mx = x + dx[i];
int my = y + dy[i];
//如果新的点走过了，或者新的点不在地图上
//或者新的点是障碍物，则跳过该点，接着判断下一个点
if(visit[mx][my]!=0||mx <1|| mx > n || my <1|| my > m || map[mx][my]==‘#’){
continue;
}else{
//如果新的点可以走则走该点，然后以该点为中心再进行搜索
visit[mx][my]=1;
dfs(mx,my);
}
}
}
int main(){
cin >> n >> m;
//输入地图，如果遇到‘S’点，则将该点的i和j记录下来。
for(int i =1;i <= n;i++){
for(int j =1;j <= m;j++){
cin >> map[i][j];
if(map[i][j]==‘S’){
sx = i;
sy = j;
}
}
}
visit[sx][sy]=1;
//从起点开始进行深搜
dfs(sx,sy);
//输出最后能获得的星星的个数
cout << cnt << endl;
return 0;
}
转自公众号：
noip案例讲解