lllhhhyyyxxx
2022-03-10 20:08
采纳率: 100%
浏览 162

Java运用BFS(广度优先搜索)解决水塘问题(全英文)

Overview: Your program will be given a "map" of wet and dry locations and you will determine how many
seperate puddles (contiguous wet areas) are depicted.
Details: The input will come from a le called input.txt which will be placed in the same directory as your
java le. The rst line of the le will have two integer values R and C which will be the number of rows and
columns in the map (simple rectangular region that can be represented by a 2-D array). Each of the next R
lines will consist of C zeroes or ones. A zero will indicate water and a one will indicate NOT water (grass?).
Two zeroes will be considered to be in the same puddle if they are either directly left/right of each other (ie
(i,j) and (i, j+1)) or directly above/below each other (ie (i,j) and (i+1, j)) or can be connected via repeated
applications of these rules.
Another (more technical) way to picture the situation is that you begin with a graph having R C vertices
each having label (i,j) where 0 i < R and 0 j < C and are divided into two sets ”Water" and “Not
Water". Vertex (i,j) shares an edge with the vertices above, below, left, and right, but not diagonal). In
other words, (i,j) is adjacent to vertices (i-1,j), (i,j-1), (i,j+1), and (i+1, j). You then remove all ”Not Water"
vertices and their incident edges.
Your program will output the number of puddles (or in the more technical description the number of com-
ponents in the graph).

Sample execution: If input.txt contains
5 10
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 0 1 1 1 0 1 1 1
1 1 0 0 0 0 0 1 1 1
1 1 1 0 0 0 0 1 1 1
then the output should be
1
If input.txt contains
10 15
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 0 1 0 1
1 1 1 1 1 0 1 1 1 1 1 0 1 0 1
1 1 1 1 1 1 0 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 0 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1 0 1 0 1 0 1
the the output should be
12

3条回答 默认 最新

相关推荐 更多相似问题