3.8DFS
洛谷题目传送门
- P1596 [USACO10OCT]Lake Counting S
- P1451 求细胞数量
- P5461 赦免战俘
- P1605 迷宫
- UVA572 油田 Oil Deposits
- P1219 [USACO1.5]八皇后 Checker Challenge
P1596 [USACO10OCT]Lake Counting S
由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。
我们用一个NxM(1<=N<=100;1<=M<=100)网格图表示。
每个网格中有水('W') 或是旱地('.')。
一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。
约翰想弄清楚他的田地已经形成了多少水坑。
给出约翰田地的示意图，确定当中有多少水坑。
输入格式:
第1行：两个空格隔开的整数：N 和 M ,
第2行到第N+1行：每行M个字符，每个字符是'W'或'.'，它们表示网格图中的一排。
字符之间没有空格。
输出格式:
一行：水坑的数量
输入样例:
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
输出样例:
3
#include<bits/stdc++.h>
using namespace std;
const int N=110;
char a[N][N];
int n,m,ans=0;
int dx[8]={-1,-1,-1, 0, 0, 1, 1, 1};
int dy[8]={-1, 0, 1,-1, 1,-1, 0, 1};
bool in(int x, int y){
if(x>=0&&x<n&&y>=0&&y<m) return 1;
return 0;
}
void dfs(int x, int y){
a[x][y]='.';
for(int i=0; i<8; i++){
int tx=x+dx[i];
int ty=y+dy[i];
if(in(tx,ty) && a[tx][ty]=='W'){
dfs(tx,ty);
}
}
}
void print(){
for(int i=0; i<n; i++){
printf("%s\n",a[i]);
}printf("\n");
}
int main(){
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin>>n>>m;
for(int i=0; i<n; i++){
scanf("%s",a[i]);
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(a[i][j]=='W') {
dfs(i,j); ans++;
// print();
}
}
}
cout<<ans<<endl;
return 0;
}
P1451 求细胞数量
一矩形阵列由数字 0 到 9 组成，数字 1 到 9 代表细胞，
细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，
求给定矩形阵列的细胞个数。
输入格式:
第一行两个整数代表矩阵大小 n 和 m。
接下来 n 行，每行一个长度为 m 的只含字符 0 到 9 的字符串，代表这个 n×m 的矩阵。
输出格式:
一行一个整数代表细胞个数。
输入样例:
4 10
0234500067
1034560500
2045600671
0000000089
输出样例:
4
数据规模与约定：对于 100% 的数据，保证 1≤n,m≤100。
#include<bits/stdc++.h>
using namespace std;
const int N=110;
char a[N][N];
int dx[8]={-1, 0, 1, 0};
int dy[8]={ 0,-1, 0, 1};
struct T{
int x,y;
};
int n,m,ans=0;
bool in(int x, int y){
if(x>=0&&x<n&&y>=0&&y<m) return 1;
return 0;
}
void print(){
for(int i=0; i<n; i++) printf("%s\n",a[i]);
printf("\n");
}
void dfs(int x,int y){
a[x][y]='0';
for(int i=0; i<4; i++){
int tx=x+dx[i];
int ty=y+dy[i];
if(in(tx,ty) && a[tx][ty]!='0'){
dfs(tx,ty);
}
}
}
int main(){
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin>>n>>m;
for(int i=0; i<n; i++) scanf("%s", a[i]);
// print();
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(a[i][j]!='0'){
dfs(i,j); ans++;
// print();
}
}
}
printf("%d\n", ans);
return 0;
}
UVA572 油田 Oil Deposits
输入多个m行n列的矩阵，用00表示输入结束。
找出有多少块石油区域，用“@”代表石油，假如两个“@”在横，竖或对角线上相邻，
就说它们位于同一区域，对于每个输入，输出一个数表示有几个石油区域。
输入样例:
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
输出样例：
0
1
2
2
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
string s[N];
int dx[8]={-1,-1,-1, 0, 0, 1, 1, 1};
int dy[8]={-1, 0, 1,-1, 1,-1, 0, 1};
bool in(int x, int y){
if(x>=0&&x<n &&y>=0&&y<m) return 1;
return 0;
}
void dfs(int x, int y){
s[x][y]='*';
for(int i=0; i<8; i++){
int tx=x+dx[i];
int ty=y+dy[i];
if(in(tx,ty) && s[tx][ty]=='@'){
dfs(tx,ty);
}
}
}
int main(){
// freopen("data.in", "r", stdin);
while(cin>>n>>m){
if(n==0&&m==0) return 0;
for(int i=0; i<n; i++) cin>>s[i];
int ans=0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(s[i][j]=='@'){
dfs(i,j); ans++;
}
}
}
cout<<ans<<endl;
}
return 0;
}