ACWing.1113 红与黑-DFS+BFS题解

ACWing.1113 红与黑-DFS+BFS题解 题目描述

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式

输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖； 2）‘#’：白色的瓷砖； 3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

输出格式

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围

1≤W,H≤20

输入样例：

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

输出样例：

45

DFS-题解

​ 本题可用DFS，也可用BFS，但DFS相对BFS要简洁一些，因此本版块主要分析DFS的写法。

​ 首先分析题目，数据范围较小，直接开二维数组储存即可。其次是图中点的储存方式，可以用字符存也可以用数字代表存，为了代码的简洁性，可以选择将对应点转成数字表示并储存，当输入扫描到‘#’标记为0，‘.’标记为1，‘@’标记为1同时记录坐标作为DFS起点。

​ 对于DFS过程，我们只需要记录能到达的点的个数，而无需测试任意两点之间的连通性，因此无需进行回溯，对于已经访问过的点标记为0即可，每次判断符合条件的点并递归搜索，这属于最简单的一类题型。题解如下：

#include 
#define xa x + a[i]
#define ya y + b[i]
using namespace std;

int graph[21][21];
int w = 0, h = 0;
int X1 = 0, Y1 = 0, cnt = 0;
const int a[] = {-1, 0, 1, 0}, b[] = {0, -1, 0, 1};

//深搜
void dfs(int x, int y){
    graph[x][y] = 0;
    cnt++;
    for(int i = 0; i < 4; i++){
        if(graph[xa][ya] == 1 && xa > 0 && xa  0 && ya > w;
        //读到终止符即停止
        if(h == 0 && w == 0) break;
        get();
    }
    return 0;
}

BFS 题解

如果用BFS做，那么关键就在于如何控制终止条件，特别注意边界就可以

#include
#include
#include
#define N 21
using namespace std;

char map[N][N];
int r,c,vis[N][N],cnt;

int a[4]={1,0,-1,0};
int b[4]={0,1,0,-1}; 

struct node
{
    int x,y;
}s,now,nxt;

bool check(int x,int y)
{
    if(!vis[x][y] && map[x][y]=='.' && x>=0 && x=0 && yc>>r && r+c) break;
        cnt=1;
        memset(vis,0,sizeof(vis));
        memset(map,0,sizeof(map));
        for(int i=0;imap[i][j];
                if(map[i][j]=='@')
                {
                    s.x=i;
                    s.y=j;
                }
            }
        }
    bfs();
    cout