首页 > 其他分享 >洛谷P1596 [USACO10OCT] Lake Counting S 题解

洛谷P1596 [USACO10OCT] Lake Counting S 题解

时间:2024-07-17 14:29:12浏览次数:8  
标签:P1596 洛谷 int 题解 Lake dfs

看别的神犇用的都是并查集,我还是用暴搜吧(doge

下面纯暴搜

#include <bits/stdc++.h>
using namespace std;
int n, m, ans; // N行M列和答案
char c[105][105]; // 存储农田的二维向量
void dfs(int x, int y) { //暴搜
	if(c[x][y + 1] == 'W'){
		c[x][y + 1]='.'; //将水坑改为陆地
		dfs(x, y + 1);
	}
	if(c[x][y - 1] == 'W'){
		c[x][y - 1] = '.'; //同上
		dfs(x, y - 1);
	}
	if(c[x + 1][y] == 'W'){
		c[x + 1][y] = '.'; //同上
		dfs(x + 1, y);
	}
	if(c[x - 1][y] == 'W'){
		c[x - 1][y] = '.';  //同上
		dfs(x - 1, y);
	}
	if(c[x + 1][y + 1] == 'W'){
		c[x + 1][y + 1] = '.'; //同上
		dfs(x + 1, y + 1);
	}
	if(c[x + 1][y - 1] == 'W'){
		c[x + 1][y - 1] = '.'; //同上
		dfs(x + 1, y - 1);
	}
	if(c[x - 1][y + 1]=='W'){
		c[x - 1][y + 1] = '.'; //同上
		dfs(x - 1, y + 1);
	}
	if(c[x - 1][y - 1] == 'W'){
		c[x - 1][y - 1] = '.'; //同上
		dfs(x - 1, y - 1);
	}
}
int main(){
    cin >> n >> m; // 输入农田的行数和列数
    // 读入农田数据
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++) cin >> c[i][j];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(c[i][j] == 'W'){
                c[i][j] = '.', ans++;  //将水坑改为陆地
                dfs(i, j); // 对每个未访问的水格子进行DFS
            }
        }
    }
    cout << ans;// 输出水坑的数量
    return 0;
}

标签:P1596,洛谷,int,题解,Lake,dfs
From: https://www.cnblogs.com/wayneoi/p/18307302

相关文章

  • CodeForces Round 898 (div 4) H题解析
     CodeForcesRound898(div4)H.Mad City                           大致思路   对于有n条边和n个点,说明这个图里面只有一个环并且两人同时开始和结束移动,所以可以得到当Valeriu进入到这个图里面的唯一......
  • 一道大「水题」 题解
    一道大水题时间限制:1000ms空间限制:256000kB题目描述[题目描述]有\(n\)个点,第\(i\)个点到第\(j\)个点有边当且仅当j是i的倍数且\(j/i\)为质数。(边是单向的)给出\(q\)组询问,每次询问从第\(1\)个点走到第\(x\)个点的方案数,对\(1e9+7\)取模。[输入格式]......
  • UNR #8 部分题题解
    由于博主水平有限,目前只有\(A,B,D\)题题解。A.最酷的排列题目描述\(T\)组数据,给定长为\(n\)的序列\(a\)和下标集合\(S\),你可以对序列进行任意次操作,每次选择一个区间并将其中元素升序排序。求\(\sum\limits_{i\inS}a_i\)的最小可能值。数据范围\(1\len,\sum......
  • 启动应用程序出现mfc80u.dll找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个mfc80u.dll文件(挑选合适的版本文件)把它放......
  • 启动应用程序出现mfc90u.dll找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个mfc90u.dll文件(挑选合适的版本文件)把它放......
  • 2024牛客暑期多校训练营1 I.Mirror Maze(题解)
    题意给一个\(n\timesm\)的二维char数组,由4种镜子组成,'\','/','-','|',镜面反射规则就是根据光线的方向和镜面的角度符合直觉的反射,然后有多组询问\(q\leq10^6\),每次给定起始位置和光线方向,求该光会经过多少面不同的镜子的反射。思路首先根据数据范围,发现肯定需要预处......
  • ARC_069 D - Menagerie 题解
    atcoder一道很有意思的模拟题啊。思路很重要。首先,我们只要知道连续两只动物的身份,就可以根据\(s\)推出所有动物的身份。不妨假设我们知道第一只和第二只动物的身份,一共有几种情况呢?用\(1\)代表羊,\(0\)代表狼。那么,共有\(2^2=4\)种情况,分别为:00011011然后我......
  • 题解|2024暑期牛客多校01
    【原文链接】太菜了就先挂4题,其他的写出来了再回来补QwQA.ABitCommon组合数学题目大意题目概括:给定两个整数nnn和m......
  • [题解]POJ2074 Line of Sight
    POJ2074LineofSight题意简述多测。给定若干条线段,全部与\(x\)轴平行。其中有\(2\)条线段表示房子和人行道(虽然翻译不是人行道就是了),保证房子在人行道上面。其他线段表示障碍物(不保证在房子和人行道之间)。请找出人行道上最长的连续部分,使得在这中间可以完整地看到房子的全......
  • CF825F String Compression题解
    思路容易想到是个动态规划。首先设\(f_i\)表示字符串前\(i\)个字符所组成的字符串的答案。状态定义好了,接下来就是考虑如何转移了。因为由\(f_i\)可以得到所有\(f_j\),其中\(i+j\lelen\),转移方程为\(f_i=f_j+x\),其中\(x\)为字符串\(i+1\)至\(j\)的最优压缩。接......