夏休み第九回——DFS
感想
短絡した後に深く探して、前の試合のように楽だと思って、テンプレートで問題を答えればいいと思っていたが、大きな考えが間違っていた.DFSにしてもBFSにしても一つの思想で、確定的なテンプレートが使用されていないような気がします.だから、最初は直接愚かに接触して、いくつかの問題をしてもできません.だから、このブログを書いて、考えを整理して、もちろん問題でメモを取ります.
DFSとBFSを2つのブログに入れて
PROBLEM
一、poj 2386
Lake Counting
Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 36404 Accepted: 18087
Description
Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.
Given a diagram of Farmer John’s field, determine how many ponds he has. Input
Output
Sample Input
10 12 W……..WW. .WWW…..WWW ….WW…WW. ………WW. ………W.. ..W……W.. .W.W…..WW. W.W.W…..W. .W.W……W. ..W…….W. Sample Output
3
Hint
OUTPUT DETAILS:
There are three ponds: one in the upper left, one in the lower left,and one along the right side. Source
USACO 2004 November
标题:いくつの水たまりがあるか探して、八つの方向に探します.アイデア:それぞれの水たまりが分割されている以上,これらの点を遍歴し,‘W’を発見したとき,DFSは,つながっている点を除いて(‘.’),水たまりの個数を1つ加算する.
CODE:
#include =0&&bmap[a][b]='.';
DFS(a,b);
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
int sum=0;
getchar();
for(int i=0;iscanf("%s",&map[i]);
for(int i=0;ifor(int j=0;jif(map[i][j]=='W')
{
DFS(i,j);
sum++;
}
printf("%d
",sum);
}
}
二、HDU 1312
Red and Black
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 21149 Accepted Submission(s): 12897
Problem Description There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.
Write a program to count the number of black tiles which he can reach by repeating the moves described above.
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.
There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.
‘.’ - a black tile ‘#’ - a red tile ‘@’ - a man on a black tile(appears exactly once in a data set)
Output
For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).
Sample Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0Sample Output
45 59 6 13
Source
Asia 2004, Ehime (Japan), Japan Domestic
Recommend
Eddy | We have carefully selected several similar problems for you: 1016 1010 1372 1242 1253
标题:該当する格子の数を入力し、各格子の色をマークし、黒い格子に遭遇したときに踏むことができ、赤い格子に遭遇したときに踏むことができず、1つの始点から踏むことができる黒い格子の数を出力することが要求される.考え方は次の問題と同じで、まず起点'@',それからDFSを見つけます.
CODE
#include =0&&bmap[a][b]=='.')
{
sum++;
map[a][b]='#';
DFS(a,b);
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF&&m&&n)
{
getchar();
sum=0;
for(int i=0;iscanf("%s",map[i]);
for(int i=0;ifor(int j=0;jif(map[i][j]=='@')
{
DFS(i,j);
break;
}
printf("%d
",sum+1);
}
}
HDU 1241は前の2つの問題と似ていて、いずれも練習問題として、簡単で、DFSの思想を初歩的に体得することができます.
三、POJ 2531
Network Saboteur
Time Limit: 2000MS Memory Limit: 65536K、Total Submissions: 13442 Accepted: 6521
Description
A university network is composed of N computers. System administrators gathered information on the traffic between nodes, and carefully divided the network into two subnetworks in order to minimize traffic between parts. A disgruntled computer science student Vasya, after being expelled from the university, decided to have his revenge. He hacked into the university network and decided to reassign computers to maximize the traffic between two subnetworks. Unfortunately, he found that calculating such worst subdivision is one of those problems he, being a student, failed to solve. So he asks you, a more successful CS student, to help him. The traffic data are given in the form of matrix C, where Cij is the amount of data sent between ith and jth nodes (Cij = Cji, Cii = 0). The goal is to divide the network nodes into the two disjointed subsets A and B so as to maximize the sum ∑Cij (i∈A,j∈B).
Input
The first line of input contains a number of nodes N (2 <= N <= 20). The following N lines, containing N space-separated integers each, represent the traffic matrix C (0 <= Cij <= 10000). Output file must contain a single integer – the maximum traffic between the subnetworks.
Output
Output must contain a single integer – the maximum traffic between the subnetworks.
Sample Input
3 0 50 30 50 0 40 30 40 0
Sample Output
90
題意はn個の点(0-n-1)を与えて、次のn行、各行はn個の数があって、第i行は第i-1個の数がn個の点からの距離を代表して、これらの点を2つの部分に分けて、2つの点セットの間の重みの最大値はいくらですかを聞きます.例えば、サンプルで0,1,2を2つの部分(1,3)と(2)の2つの部分に分けると、最長距離はmap[1][2]+map[3][2]=90となる.アイデア:集合中の要素1のみから{1}->{1,2}->{1,2,3}->{1,3}を巡って最大値をとる
CODE
#include