HDU1312（BFS,DFS模板题）

68 阅读 0 评论 45 点赞

我是靠谱客的博主坚强小霸王，最近开发中收集的这篇文章主要介绍HDU1312（BFS,DFS模板题），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

描述

这有一间铺满方形瓷砖的长方形客房。每块瓷砖的颜色是红色或者黑色。一个人站在一块黑色瓷砖上，他可以从这块瓷砖移动到相邻（即，上下左右）的四块瓷砖中的一块。但是他只能移动到黑色瓷砖上，而不能移动到红色瓷砖上。编写一个程序，通过重复上述动作来计算他可以达到的黑色瓷砖的数量。

Input

输入包含多组数据。每组数据包含两个正整数W和H; H表示瓷砖的行数，W表示瓷砖的列数。 W和H不超过20。

瓷砖的颜色用字符表示，如下所示。

‘.’ - 黑色瓷砖
‘#’ - 红色瓷砖
‘@’ - 站在黑色瓷砖上的人（每组数据中只有一个）

Output

对于每组数据，你的程序应输出一行，其中包含他可以到达的黑色瓷砖数目。（站着的黑色瓷砖也要包含在内）

样例输入

6 9
…#.
…#
…
…
…
…
…
#@…#
.#…#.
11 9
.#…
.#.#######.
.#.#…#.
.#.#.###.#.
.#.#…@#.#.
.#.#####.#.
.#…#.
.#########.
…
11 6
…#…#…#…
…#…#…#…
…#…#…###
…#…#…#@.
…#…#…#…
…#…#…#…
7 7
…#.#…
…#.#…
###.###
…@…
###.###
…#.#…
…#.#…
0 0

样例输出

45
59
6
13

BFS

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n, m, sx, sy;
const int N = 1e2+10;
char s[N][N];
int use[N][N];
int qwe[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//上下左右 
bool jg(int x, int y)//判断是否能走 
{
if (x<1 || x>n || y<1 || y>m)//超出边界 
return false;
if (s[x][y] == '#')//为# 
return false;
if (use[x][y] == 1)//走过了 
return false;
return true;
}
void bfs()
{
memset(use, 0, sizeof use);//初始化 
queue<pair<int, int> > que;
que.push(pair<int, int>(sx, sy));
use[sx][sy] = 1;//标记找到的位子 
int sum = 0;
while (!que.empty())//当前位子的上下左右能否走 
{
pair<int, int> u = que.front();
que.pop();
sum++;
for (int i = 0; i < 4; i++)
{
int nx = u.first + qwe[i][0];
int ny = u.second + qwe[i][1];
if (jg(nx, ny))
{
use[nx][ny] = 1;
que.push(pair<int, int>(nx, ny));
}
}
}
printf("%dn", sum);
}
int main()
{
while (scanf("%d %d", &m, &n), m + n)
{
for (int i = 1; i <= n; i++)
scanf("%s", s[i] + 1);
for (int i = 1; i <= n; i++)//找当前位子 
{
for (int j = 1; j <= m; j++)
{
if (s[i][j] == '@')
{
sx = i;
sy = j;
}
}
}
bfs();
}
return 0;
}

DFS

#include<cstdio>
#include<queue>
#include<string.h>
using namespace std;
const int N = 1e2 + 10;
int n, m, sx, sy;
int ans;
char s[N][N];
int use[N][N];
int qwe[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };//上下左右 
bool jg(int x, int y)//判断是否能走 
{
if (x<1 || x>n || y<1 || y>m)//超出边界 
return false;
if (s[x][y] == '#')//为# 
return false;
if (use[x][y])//走过了 
return false;
return true;
}
void dfs(int x, int y)
{
if(jg(x,y))
{
use[x][y] = 1;//标记找到的位子
ans++;
for (int i = 0; i < 4; i++)
{
int nx = x + qwe[i][0];
int ny = y + qwe[i][1];
dfs(nx, ny);
}
}
else
return;
}
int main()
{
while (scanf("%d %d", &m, &n), m + n)
{
memset(use, 0, sizeof use);//初始化 
for (int i = 1; i <= n; i++)
scanf("%s", s[i] + 1);
int x, y;
for (int i = 1; i <= n; i++)//找当前位子 
{
for (int j = 1; j <= m; j++)
{
if (s[i][j] == '@')
{
x = i;
y = j;
}
}
}
ans = 0;
dfs(x, y);
printf("%dn", ans);
}
return 0;
}