HHUOJ 1114

1114: 屁屁上的巴掌

时间限制: 1 Sec  内存限制: 128 MB
提交: 71  解决: 38
[提交][状态][讨论版][命题人:外部导入]

题目描述

小新是个调皮的孩子,他总是会把衣服搞脏,他的妈妈美伢非常的生气,于是在《和妈妈的约定条款》加上了第三百七十七条:小新衣服上每有一块污渍妈妈就会打小新的小屁屁一下作为惩罚。我们规定如果两个污渍相邻(直接相邻的上下左右、左上、左下,右上、右下都算相邻)那么它们就算是一块污渍。现在小新又把衣服搞脏了,请你帮他算一算他的屁股上会挨几巴掌?

输入

输入将会包含多组测试数据,每组测试数据将会以m和n开头,表示将会用m行n列的网格代表小新的衣服,如果m=0输入结束;1 <= m <= 100 并且1 <= n <= 100.接下来是m行n列的网格,网格中’@’代表污渍,’*’代表没有污渍。

输出

对于每组数据,请输出小新屁股挨到的巴掌的数量。

样例输入

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

样例输出

0
1
2
2

DFS,一开始想,写个函数判断周围有没有其他污点就行了,写着写着发现要用递归,然后才知道要用深搜(迟钝。。想通之后就简单了

另外,初始化时,scanf貌似不能直接读入二维数组,会把回车读进去,用cin就行了,要是以后卡了输入怎么办就不知道了,挖坑待填。。

校赛倒计时,加油!

以下是AC代码:

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <cstring>
 4 #include <algorithm>
 5
 6 using namespace std;
 7
 8 const int maxn = 105;
 9 char board[maxn][maxn];
10 int dx[] = { -1,-1,-1,0,1,1,1,0 };
11 int dy[] = { -1,0,1,1,1,0,-1,-1 };
12 int n, m;
13 void dfs(int x, int y)
14 {
15     for (int i = 0; i < 8; i++)
16     {
17         int tempx = x + dx[i];
18         int tempy = y + dy[i];
19         if (board[tempx][tempy] == ‘@‘)
20         {
21             board[tempx][tempy] = ‘*‘;
22             dfs(tempx, tempy);
23         }
24     }
25 }
26 int main(void)
27 {
28     int n, m;
29     while (scanf_s("%d%d", &m, &n) != EOF && m != 0)
30     {
31         memset(board, ‘*‘, sizeof(board));
32         int i, j;
33         int count;
34         for (i = 1; i <= m; ++i)
35         {
36             for (j = 1; j <= n; ++j)
37             {
38                 cin >> board[i][j];
39             }
40         }
41         for (i = 0; i <= m + 1; ++i)
42         {
43             board[i][0] = ‘#‘;
44             board[i][n + 1] = ‘#‘;
45         }
46         for (j = 0; j <= n + 1; ++j)
47         {
48             board[0][j] = ‘#‘;
49             board[m + 1][j] = ‘#‘;
50         }
51         count = 0;
52         for (i = 1; i <= m; ++i)
53         {
54             for (j = 1; j <= n; ++j)
55             {
56                 if (board[i][j] == ‘@‘)
57                 {
58                     dfs(i, j);
59                     count++;
60                 }
61             }
62         }
63         cout << count << endl;
64     }
65     return 0;
66 }

 

原文地址:https://www.cnblogs.com/CofJus/p/10079554.html

时间: 12-06

HHUOJ 1114的相关文章

HDU 1114 (dp 完全背包)

鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1114 Problem Description Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The i

[2016-03-27][HDU][1114][Piggy-Bank]

时间:2016-03-27 16:37:56 星期日 题目编号:[2016-03-27][HDU][1114][Piggy-Bank] 遇到的问题:注意f == e的情况,即dp[0] = 0; #include <cstring> #include <cstdio> #include<algorithm> using namespace std; int dp[10000 + 10]; int w[500 + 10],c[500 + 10]; int main(){

hdu 1114 Piggy-Bank 完全背包

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1114 题意分析:给出存钱罐存钱前后的重量,以及钱的种类及其价值和种类, 要求装满存钱罐最小的价值.  完全背包 /*Piggy-Bank Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13578 Accepted Submission(s):

hdu 1114 Piggy-Bank

题目: 链接:点击打开链接 题意: 知道存钱罐的质量和装满硬币的存钱罐的质量,然后是不同硬币的价值和质量,求出存钱罐里钱币的最小价值. 算法: 完全背包问题,银币的个数是不限的. 思路: 状态转移方程:j = 0时,价值为0 dp[j] = min(dp[j],dp[j-w[i]]+v[i]);//表示质量为j的钱币,含有的最小的价值 代码: #include<iostream> #include<cstdio> #include<cstring> using name

Ural 1114 Boxes

Boxes Time Limit: 600ms Memory Limit: 16384KB This problem will be judged on Ural. Original ID: 111464-bit integer IO format: %lld      Java class name: (Any) N boxes are lined up in a sequence (1 ≤ N ≤ 20). You have A red balls and B blue balls (0 ≤

HDU 1114 Piggy-Bank 猪仔储钱罐(AC代码)完全背包(容量需满,价值最小)

1 #include <iostream> 2 #define MAX 0xfffffff 3 using namespace std; 4 //要求:1.刚好装满 2.总价值最小 5 int value[501]; 6 int weight[501]; 7 int dp[10010]; 8 int min(int a,int b) 9 { 10 return a<b?a:b; 11 } 12 int cal(int v,int n) //空间.种类 13 { 14 int i,j; 1

[HDU 1114] Piggy-Bank (动态规划)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1114 简单完全背包,不多说. 1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #include <map> 6 #include <iterator> 7 #include <vector> 8 using

[计数dp] ural 1114. Boxes

题目链接: http://acm.timus.ru/problem.aspx?space=1&num=1114 1114. Boxes Time limit: 0.6 second Memory limit: 64 MB N boxes are lined up in a sequence (1 ≤ N ≤ 20). You have A red balls and B blue balls (0 ≤ A ≤ 15, 0 ≤ B ≤ 15). The red balls (and the blu

csuoj 1114: 平方根大搜索

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1114 1114: 平方根大搜索 Time Limit: 5 Sec  Memory Limit: 128 MBSubmit: 118  Solved: 60[Submit][Status][Web Board] Description 在二进制中,2的算术平方根,即sqrt(2),是一个无限小数1.0110101000001001111... 给定一个整数n和一个01串S,你的任务是在sqrt(

Acdream 1114 Number theory 莫比乌斯反演

http://acdream.info/problem?pid=1114 题目大意,给你一个序列a,求出这个序列中互质数的有多少对.其中所有的整数的都小于等于222222. f(d) 为 gcd 恰好为 d 的数的对数, F(d) 为 gcd 为 d 的倍数的对数, μ(d) 表示莫比乌斯函数 F(d) = ∑ f(n) 其中( n % d == 0 ) 莫比乌斯反演一下就可以得到, f(d) = ∑ μ(n / d) * F(n) 其中( n % d == 0) 所以我们最后所要的答案就是 f