这种普通走迷宫的题,还是最好用bfs,毕竟复杂度是比dfs低的。但我这用dfs讲解。
具体思路就不做详解,看代码注释。
Code
#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[105][105];
int dx[8] = {0,1,-1,0,-1,1,-1,1};//搜索的八个方向常量,x
int dy[8] = {1,0,0,-1,-1,1,1,-1};//同上,y
void dfs(int x,int y){
for(int i=0;i<8;i++){//枚举八个方向
int tx = x + dx[i];//记录变化的x坐标
int ty = y + dy[i];//同上,y坐标
if(a[tx][ty] == 'W' && tx >= 1 && tx <= n && ty >= 1 && ty <= m){//判断是否是水洼以及有没有越界
a[tx][ty] = '.';//将其变成'.',防止重复
dfs(tx,ty);//从这个地方继续dfs。
}
}
}
int main(){
cin >> n >> m;//输入地图长宽
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >> a[i][j];//输入地图
}
}
int num=0;//最终答案初始化
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j] == 'W'){//寻找水洼
num ++;//将水洼个数加1
a[i][j] = '.';//为防止dfs重复计算将其变成'.'
dfs(i,j);//开始dfs
}
}
}
cout << num;//输出答案
return 0;
}
标签:P1596,tx,ty,int,水洼,dfs,USACO10OCT,&&,Counting
From: https://blog.csdn.net/KAFKAut/article/details/140993005