hdu1241

dfs(31ms)

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, m;
int dist[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
char s[105][105];

void dfs(int x, int y){
	for (int i = 0; i < 8; i++){
		int xx = x + dist[i][0], yy = y + dist[i][1];
		if(x < 1 || x > n || y < 1 || y > m) continue;
		if(s[xx][yy] == '@'){
			s[xx][yy] = '*';
			dfs(xx, yy);
		}
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	while(scanf("%d %d", &n, &m) == 2){
		if(!n && !m) break;
		for (int i = 1; i <= n; i++){
			scanf("%s", s[i] + 1);
		}
		int ans = 0;
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= m; j++){
				if(s[i][j] == '@'){
					ans++;
					s[i][j] = '*';
					dfs(i, j);
				}
			}
		}
		printf("%d\n", ans);
	}

	return 0;
}
/**/

并查集(15ms)

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, m;
int f[10005];
char s[105][105];
int dist[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1};

int Find(int x){
	return x == f[x] ? x : Find(f[x]);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	while(scanf("%d %d", &n, &m) == 2){
		if(!n && !m) break;
		for (int i = 1; i <= n * m; i++){
			f[i] = i;
		}
		for (int i = 1; i <= n; i++){
			scanf("%s", s[i] + 1);
		}
		set<int>st;
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= m; j++){
				if(s[i][j] == '@'){
					int X = Find((i - 1) * m + j);
					for (int k = 0; k < 8; k++){
						int x = i + dist[k][0], y = j + dist[k][1];
						if(x < 1 || x > n || y < 1 || y > m) continue;
						if(s[x][y] == '@'){
							int Y = Find((x - 1) * m + y);
							if(X != Y){
								f[Y] = X;
							}
						}
					}
				}
			}
		}
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= m; j++){
				if(s[i][j] == '@'){
					f[(i - 1) * m + j] = Find((i - 1) * m + j);
					st.insert(f[(i - 1) * m + j]);
				}
			}
		}
		printf("%d\n", st.size());
	}

	return 0;
}

 

全部评论

相关推荐

把实习生当正职使昨天第一天就加班,晚上连口饭都没吃上,以后日子咋过,我不想干了
码农索隆:实习不怕忙,就怕干的活重复且没难度,要干就干那种有深度有难度的任务,这样才能快速的提升
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-27 15:19
简历上能写3个月吗?
码农索隆:大胆写,主要你能把实习经历包装好,可以看一下我这篇帖子https://www.nowcoder.com/share/jump/4888395581180798063
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
点赞 评论 收藏
分享
06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务