SDUT Balloons 和 HDU 1241 Oil Deposits
题目共同解法
都是求某一类连接成块共有多少块，那么对每一块dfs，运行多少次dfs便有多少块
Description
Both Saya and Kudo like balloons. One day, they heard that in the central park, there will be thousands of people fly balloons to pattern a big image. They were very interested about this event, and also curious about the image. Since there are too many balloons, it is very hard for them to compute anything they need. Can you help them? You can assume that the image is an N\N matrix, while each element can be either balloons or blank. Suppose element A and element B* are both balloons. They are connected if:
题目链接 http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/2152.html
i) They are adjacent; ii) There is a list of element C1, C2, … , C**n, while A and C1 are connected, C1 and C2 are connected …C**n and B are connected. And a connected block means that every pair of elements in the block is connected, while any element in the block is not connected with any element out of the block. To Saya, element A(xa,ya)and B(xb,yb) is adjacent if |xa-xb| + |ya-yb| ≤ 1 But to Kudo, element A(xa,ya) and element B (xb,yb) is adjacent if |xa-xb|≤1 and |ya-yb|≤1 They want to know that there’s how many connected blocks with there own definition of adjacent?
Input
The input consists of several test cases. The first line of input in each test case contains one integer N (0<N≤100), which represents the size of the matrix. Each of the next N lines contains a string whose length is N, represents the elements of the matrix. The string only consists of 0 and 1, while 0 represents a block and 1represents balloons. The last case is followed by a line containing one zero.
Output
For each case, print the case number (1, 2 …) and the connected block’s numbers with Saya and Kudo’s definition. Your output format should imitate the sample output. Print a blank line after each test case.
Sample Input
5
11001
00100
11111
11010
10010
0
Sample Output
Case 1: 3 2
注意
1.细节
2.输出格式：“Case” 、 空行
Code
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int a, b, n;
string s[N];
bool visa[N][N];
bool visb[N][N];
int dx[] = {-1, 1, 0, 0, -1, 1, 1, -1};
int dy[] = {0, 0, 1, -1, 1, 1, -1, -1};
void dfsa(int x, int y)
{
visa[x][y] = 1;
for(int i = 0; i < 4; ++i)
{
int xx = x + dx[i];
int yy = y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < n && !visa[xx][yy] && s[xx][yy] == '1')
{
visa[xx][yy] = 1;
dfsa(xx, yy);
}
}
return ;
}
void dfsb(int x, int y)
{
visb[x][y] = 1;
for(int i = 0; i < 8; ++i)
{
int xx = x + dx[i];
int yy = y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < n && !visb[xx][yy] && s[xx][yy] == '1')
{
visb[xx][yy] = 1;
dfsb(xx, yy);
}
}
return ;
}
int main()
{
int cnt = 1;
while(cin >> n && n)
{
memset(visa, 0, sizeof(visa));
memset(visb, 0, sizeof(visb));
a = 0, b = 0;
for(int i = 0; i < n; ++i)
cin >> s[i];
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
if(s[i][j] == '1')
{
if(!visa[i][j])
{
dfsa(i, j);
a++;
}
if(!visb[i][j])
{
dfsb(i, j);
b++;
}
}
cout << "Case " << cnt << ": " << a << ' ' << b << '\n' << '\n';
cnt++;
}
}
Description
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1241
Input
The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*’, representing the absence of oil, or `@’, representing an oil pocket.
Output
For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.
Sample Input
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
Sample Output
0
1
2
2
Code
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int n, m;
string s[N];
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
void dfs(int x, int y)
{
s[x][y] = '*';
for(int i = 0; i < 8; ++i)
{
int xx = x + dx[i];
int yy = y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && s[xx][yy] == '@')
{
s[xx][yy] = '*';
dfs(xx, yy);
}
}
}
int main()
{
while(~scanf("%d%d", &n, &m))
{
if(n == 0 && m == 0)
break;
int ans = 0;
for(int i = 0; i < n; ++i)
cin >> s[i];
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(s[i][j] == '@')
{
dfs(i, j);
ans++;
}
cout << ans << '\n';
}
return 0;
}