【信息学奥赛课课通】 瓷砖

本题目源于《信息学奥赛课课通》

原题链接

洛谷也有改版的题目

题目描述

在一个 w×hw×hw×h 的矩形广场上，每一块 1×11×11×1 的地面都铺设了红色或黑色的瓷砖。小林同学站在某一块黑色的瓷砖上，他可以从此处出发，移动到上、下、左、右四个相邻的且是黑色的瓷砖上。现在，他想知道，通过重复上述移动所能经过的黑色瓷砖数。注意，小林站的位置也算一块黑色瓷砖。

输入

第 111 行为 h、w、2≤w、h≤50，h、w、2≤w、h≤50，h、w、2≤w、h≤50，之间有一个空格隔开。

以下为 111 个 www 行 hhh 列的二维字符矩阵，每个字符为“.”“#”“@”，分别表示该位置为黑色的瓷砖、红色的瓷砖、小林的初始位置。

输出

输出一行一个整数，表示小林从初始位置出发经过的黑色瓷砖数。

样例输入

11 9.#..........#.#######..#.#.....#..#.#.###.#..#.#..@#.#..#.#####.#..#.......#..#########............

样例输出

59

分析：

一看到这种题目就知道应该用深搜（百度优先搜索）

既然“#”表示不能走，那么也就可以忽略不计（根本不用去考虑这个方面）数据也不算很大，可以轻松解决（不会超时）我们只需要去探测“.”的次数

搜就完事

下面！上代码！

#include<bits/stdc++.h>//Van能头using namespace std;int m,n,ans=1;char c[101][101];bool t[101][101];//用来做标记，判断这个点搜过没有，可以降低时间复杂度int gx[4]={1,-1,0,0},gy[4]={0,0,1,-1}; //设置搜索的方向，四个对应的是上下左右 void s(int x,int y){for(register int i=0;i<4;++i){//卡常技巧（可有可无），"register"以及++前置 if(c[x+gx[i]][y+gy[i]]=='.' && !t[x+gx[i]][y+gy[i]]){//如果是“.”就搜索，而且保证它没有被标记过t[x+gx[i]][y+gy[i]]=1;//往各个方向进行搜索ans++;//搜到了，次数就+1s(x+gx[i],y+gy[i]);//继续搜索（递归）}}return ;//退出}int main(){cin>>m>>n;int x,y;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>c[i][j];if(c[i][j]=='@'){//就是说：输入的时候，如果读到“@”就把这个点标记为起点x=i;//设置初始位置（起点）y=j;}}}s(x,y);//从起点开搜cout<<ans<<endl;return 0;}

哥哥（姐姐）们不要老师复制代码啊，要自己思考，我已经讲的很详细了！

注：如有雷同，纯属巧合