11月9日星期天 9:00-12:00
S07L03【基础】数池塘（四方向）
描述
农夫约翰的农场可以表示成N*M（1≤N≤100≤M≤100）个方格组成的矩形。由于近日的降雨，在约翰农场上的不同地方形成了池塘。每一个方格或者有积水（‘W’）或者没有积水（’.’）。农夫约翰打算数出他的农场上共形成了多少池塘。一个池塘是一系列相连的有积水的方格，每一个方格周围的四个方格都被认为是与这个方格相连的。现给出约翰农场的图样，要求输出农场上的池塘数。
输入描述
第1行：由空格隔开的两个整数：N和M
第2…N+1行：每行M个字符代表约翰农场的一排方格的状态。每个字符或者是’W’或者是’.’，字符之间没有空格。
输出描述
输出只有1行，输出约翰农场上的池塘数
用例输入 1
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
用例输出 1
13
代码
解析:
问有多少个池塘,其实就是问有多少个W连在一起的区域.
当我们遇到一个W的时候,把他的坐标当成起点,进行深度优先搜索,搜索过的点变成. 这样搜索完之后一个池塘就没了,我们就计数+1
这样我们进行了多少次深搜 就有多少片池塘
#include<bits/stdc++.h>
using namespace std;
int n,m,jishu;
char num[110][110];
int fx[4]={1,-1,0,0};
int fy[4]={0,0,1,-1};
void dfs(int x,int y){
num[x][y]='.';
for(int i=0;i<4;i++){
int xx = fx[i]+x;
int yy = fy[i]+y;
//判断是否可达 如是否出界 是否为障碍物 是否走过
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&num[xx][yy]=='W'){
dfs(xx,yy);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>num[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//遇到w开始进行搜索,并且标记为.
if(num[i][j]=='W'){
dfs(i,j);
jishu++;
}
}
}
cout<<jishu;
return 0;
}
S07L04【基础】走出迷宫的最少步数
描述
一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。
输入描述
第一行是两个整数，R和C，代表迷宫的行数和列数。（ 1<= R，C <= 40)
接下来是R行，每行C个字符，代表整个迷宫。空地格子用’.‘表示，有障碍物的格子用’#‘表示。迷宫左上角和右下角都是’.’。
输出描述
输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。
用例输入 1
5 5
..###
#....
#.#.#
#.#.#
#.#..
用例输出 1
9
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,jishu,mmin=INT_MAX,num2[110][110];
char num[110][110];
int fx[4]={1,-1,0,0};
int fy[4]={0,0,1,-1};
void dfs(int x,int y,int k){
num2[x][y]=k;
for(int i=0;i<4;i++){
int xx = fx[i]+x;
int yy = fy[i]+y;
//判断是否可达 如是否出界 是否为障碍物 是否走过
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&num[xx][yy]=='.'&&num2[xx][yy]>k+1){
dfs(xx,yy,k+1);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>num[i][j];
num2[i][j]=INT_MAX;
}
}
dfs(1,1,1);
cout<<num2[n][m];
return 0;
}
S07L05【基础】迷宫的第一条出路
描述
已知一N×N的迷宫，允许往上、下、左、右四个方向行走，现请你按照左、上、右、下顺序进行搜索，找出第一条从左上角到右下角的路径。
输入描述
输入数据有若干行，第一行有一个自然数N（N≤20），表示迷宫的大小，其后有N行数据，每行有N个0或1（数字之间没有空格，0表示可以通过，1表示不能通过），用以描述迷宫地图。入口在左上角（1，1）处，出口在右下角（N，N）处。所有迷宫保证存在从入口到出口的可行路径。
输出描述
输出数据仅一行，为按照要求的搜索顺序找到的从入口到出口的第一条路径（搜索顺序：左、上、右、下）。
用例输入 1
4
0001
0100
0010
0110
用例输出 1
(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4)
代码
#include<bits/stdc++.h>
using namespace std;
char num[21][21];
int n,num2[410][2];
int fx[4]={0,-1,0,1};
int fy[4]={-1,0,1,0};
//更新num2数组
void dfs(int x,int y,int k){
// cout<<x<<" "<<y<<" "<<k<<endl;
//将坐标存入num2
num2[k][0] = x;
num2[k][1] = y;
num[x][y]=1;//标记
if(x==n&&y==n){
for(int i=1;i<=k;i++){
//(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4)
cout<<'('<<num2[i][0]<<','<<num2[i][1]<<")";
if(i!=k) cout<<"->";
}
}
for(int i=0;i<4;i++){
int xx = fx[i]+x;
int yy = fy[i]+y;
if(num[xx][yy]=='0'){
dfs(xx,yy,k+1);
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>num[i][j];
}
}
dfs(1,1,1);
return 0;
}