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

洛谷P1596 [USACO10OCT] Lake Counting S

时间:2024-08-07 15:23:45浏览次数:14  
标签:P1596 tx ty int 水洼 dfs USACO10OCT && Counting

这种普通走迷宫的题,还是最好用bfs,毕竟复杂度是比dfs低的。但我这用dfs讲解。
具体思路就不做详解,看代码注释。

Code

#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[105][105];
int dx[8] = {0,1,-1,0,-1,1,-1,1};//搜索的八个方向常量,x
int dy[8] = {1,0,0,-1,-1,1,1,-1};//同上,y
void dfs(int x,int y){
	for(int i=0;i<8;i++){//枚举八个方向
		int tx = x + dx[i];//记录变化的x坐标
		int ty = y + dy[i];//同上,y坐标
		if(a[tx][ty] == 'W' && tx >= 1 && tx <= n && ty >= 1 && ty <= m){//判断是否是水洼以及有没有越界
			a[tx][ty] = '.';//将其变成'.',防止重复
			dfs(tx,ty);//从这个地方继续dfs。
		}
	}
}
int main(){
	cin >> n >> m;//输入地图长宽
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> a[i][j];//输入地图
		}
	}
	int num=0;//最终答案初始化
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j] == 'W'){//寻找水洼
				num ++;//将水洼个数加1
				a[i][j] = '.';//为防止dfs重复计算将其变成'.'
				dfs(i,j);//开始dfs
			}
		}
	}
	cout << num;//输出答案
	return 0;
}

标签:P1596,tx,ty,int,水洼,dfs,USACO10OCT,&&,Counting
From: https://blog.csdn.net/KAFKAut/article/details/140993005

相关文章

  • COUNTING-SORT(计数排序) and
    计数排序             计数排序假设n个输入元素(适用于小范围区间)中的每一个都是在0到k区间内的一个整数,其中k为某个整数。当k=O(n)时,排序的运行时间为.    计数排序的基本思想:对每一个输入的元素x,确定小于x的元素个数。利用这一信息,就可以直接把x......
  • 题解:CF1608F MEX counting
    题解:CF1608FMEXcounting与其他题解不同,本篇题解是运用辅助数组$g$来解决问题。虽然代码可能要繁琐一点,但是辅助数组的思路适用范围更广一点。首先还是转化为前$i$个数的$mex$在区间$[l_i,r_i]$内。我们用dp数组$f_{i,x,c}$表示处理到了第$i$个数,当前的mex为......
  • YC322A [ 20240724 CQYC NOIP 模拟赛 T4 ] 庫的 序计数(counting)
    题意给定一棵树\(T\),每次操作在某个点下方接上\(k\)个儿子。询问期望多少次排列,使得\(a_{fa_i}<a_i\)。保证\(k\)是偶数,对\(65536\)取模。\(n\le10^5,k\le2\times10^9\)。Sol考虑假如已经确定了一棵树的形态,如何求出最终的答案?可以发现对于每一个节点......
  • 洛谷P1596 [USACO10OCT] Lake Counting S 题解
    看别的神犇用的都是并查集,我还是用暴搜吧(doge下面纯暴搜#include<bits/stdc++.h>usingnamespacestd;intn,m,ans;//N行M列和答案charc[105][105];//存储农田的二维向量voiddfs(intx,inty){//暴搜 if(c[x][y+1]=='W'){ c[x][y+1]='.';//将水坑改为......
  • 1004 Counting Leaves(dfs):邻接表版:写的太多了
    Afamilyhierarchyisusuallypresentedbyapedigreetree.Yourjobistocountthosefamilymemberswhohavenochild.InputSpecification:Eachinputfilecontainsonetestcase.Eachcasestartswithalinecontaining0<N<100,thenumberofnode......
  • [题解]AT_abc216_f [ABC216F] Max Sum Counting
    思路首先,不难发现,对于本题将\(a,b\)合成一个序列,并按照\(a_i\)排序的答案不会发生变化。所以,我们可以直接排序,那么,我们当前枚举到的\(a_i\)就是当前的\(\max(a_i)\)。定义\(dp_{i,j,0/1}\)表示在\(1\simi\)中,选择的\(b_i\)之和为\(j\),并且第\(i\)个数不选/选......
  • CF1919E Counting Prefixes
    CF1919ECountingPrefixesRating:2600题目大意有一个由-1与1构成的数列\(A\)。告诉你它的前缀和升序排序的数列\(P\)。求有多少个满足方案的数列\(A\)。多组数据,其中\(A\)的长度\(n\)有。\(\sumn\leq5000\)。解题思路首先我们考虑枚举\(s=\sumA\)。我......
  • Counting Rhyme
    题面翻译给定长度为\(n\)的序列\(a\)。对于\(1\leqi<j\leqn\),若不存在\(k\in[1,n]\)使得\(a_k\mida_i\)且\(a_k\mida_j\)那么\((i,j)\)是好的。求出好的数对数量。\(1\lea_i\len\leq10^6\)。题目描述Youaregivenanarrayofintegers$a_1,a_2,\ldot......
  • 题解:P8267 [USACO22OPEN] Counting Liars B & U208878 晴天
    其实,这个题,只需要最简单的枚举,加上最简单的二分查找即可~\(1\leN\le1000\)?枚举吧~咋枚举?显然,最好状态下Bessie的位置一定是某个\(p_i\),否则差一个就会导致有个奶牛要说谎。所以我们枚举(理论来讲要先去个重,这样快一点,不过貌似数据没有重的~)\(p_i\),每次遍历这帮奶牛看看有......
  • 挑战程序设计竞赛 2.1章习题 poj 3046 Ant Counting
    https://vjudge.net.cn/problem/POJ-3046#author=GPT_zh有一天,贝西在蚂蚁山里探头探脑,看着蚂蚁们来来回回地觅食。她发现很多蚂蚁都是兄弟姐妹,彼此无法区分。她还发现,有时只有一只蚂蚁去觅食,有时几只,有时全部。这就产生了大量不同组合的蚂蚁!有点数学天赋的贝茜开始琢磨起来......