flood fill.htm

总共80多道题的POJ详细解题报告

    <TD align=middle>-2</TD></TR>
  <TR>
    <TD align=middle>7</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle>8</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle><B>9</B></TD>
    <TD align=middle><B>2</B></TD></TR></TBODY></TABLE></CENTER>
<P>The terminating condition does not hold ( <TT>num_visited</TT> = 3), so the 
the search through for nodes assigned to component -2 starts again. Node 5 is 
the first one found. 
<CENTER>
<TABLE border=1>
  <TBODY>
  <TR>
    <TD align=middle>Node</TD>
    <TD align=middle>Component</TD></TR>
  <TR>
    <TD align=middle>1</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle>2</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle>4</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle>5</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle><B>6</B></TD>
    <TD align=middle><B>-2</B></TD></TR>
  <TR>
    <TD align=middle>7</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle>8</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle>9</TD>
    <TD align=middle>2</TD></TR></TBODY></TABLE></CENTER>
<P>Node 6 is the next node found to be in component -2. 
<CENTER>
<TABLE border=1>
  <TBODY>
  <TR>
    <TD align=middle>Node</TD>
    <TD align=middle>Component</TD></TR>
  <TR>
    <TD align=middle>1</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle>2</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle>4</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle>5</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle><B>6</B></TD>
    <TD align=middle><B>2</B></TD></TR>
  <TR>
    <TD align=middle>7</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle>8</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle>9</TD>
    <TD align=middle>2</TD></TR></TBODY></TABLE></CENTER>
<P>No more nodes are found assigned to component -2, but the terminating 
condition does not hold, so one more pass through the nodes is performed, 
finding no nodes assigned to component -2. Thus, the search for unassigned nodes 
continue from node 2, finding node 3 unassigned. 
<CENTER>
<TABLE border=1>
  <TBODY>
  <TR>
    <TD align=middle>Node</TD>
    <TD align=middle>Component</TD></TR>
  <TR>
    <TD align=middle>1</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle>2</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle><B>3</B></TD>
    <TD align=middle><B>-2</B></TD></TR>
  <TR>
    <TD align=middle>4</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle>5</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle>6</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle>7</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle>8</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle>9</TD>
    <TD align=middle>2</TD></TR></TBODY></TABLE></CENTER>
<P>Node 3 is processed. 
<CENTER>
<TABLE border=1>
  <TBODY>
  <TR>
    <TD align=middle>Node</TD>
    <TD align=middle>Component</TD></TR>
  <TR>
    <TD align=middle>1</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle>2</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle>3</TD>
    <TD align=middle>3</TD></TR>
  <TR>
    <TD align=middle>4</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle>5</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle>6</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle>7</TD>
    <TD align=middle>2</TD></TR>
  <TR>
    <TD align=middle>8</TD>
    <TD align=middle>1</TD></TR>
  <TR>
    <TD align=middle>9</TD>
    <TD align=middle>2</TD></TR></TBODY></TABLE></CENTER>
<P>From here, the algorithm eventually terminates, as there are no more nodes 
assigned to component -2 and no unassigned nodes. The three components of the 
graph have been determined, along with the component to which each node belongs. 

<H4>Problem Cues</H4>
<P>Generally, these types of problem are fairly clear. If it asks for sets of 
"connected" things, it's probably asking for components, in which case flood 
fill works very well. Often, this is a step in solving the complete problem. 
<H4>Extensions</H4>
<P>The notion of ``components'' becomes muddied when you go to directed graphs. 
<P>However, the same flooding idea can be used to determine the points which are 
reachable from any given point even in a directed graph. At each recursive step, 
if the point isn't marked already, mark the point as reachable and recurse on 
all of its neighbors. 
<P>Note that to determine which points can reach a given point in a directed 
graph can be solved the same, by looking at every arc backwards. 
<H4>Sample Problems</H4>
<H5>Company Ownership [abridged, IOI 93]</H5>
<P>Given: A weighted directed graph, with weights between 0 and 100. 
<P>Some vertex A ``owns'' another vertex B if: 
<UL>
  <LI>A = B 
  <LI>There is an arc from A to B with weight more than 50. 
  <LI>There exists some set of vertices <I>C <SUB>1</SUB></I> through <I>C 
  <SUB>k</SUB></I> such that A owns <I>C <SUB>1</SUB></I> through <I>C 
  <SUB>k</SUB></I>, and each vertex has an arc of weight <I>x <SUB>1</SUB></I> 
  through <I>x <SUB>k</SUB></I> to vertex B, and <I>x <SUB>1</SUB></I> + <I>x 
  <SUB>2</SUB></I> + ... + <I>x <SUB>k</SUB></I> &gt; 50. </LI></UL>
<P>Find all (a,b) pairs such that a owns b. 
<P>Analysis: This can be solved via an adaptation of the calculating the 
vertices reachable from a vertex in a directed graph. To calculate which 
vertices vertex A owns, keep track of the ``ownership percentage'' for each 
node. Initialize them all to zero. Now, at each recursive step, mark the node as 
owned by vertex A and add the weight of all outgoing arcs to the ``ownership 
percentages.'' For all percentages that go above 50, recurse into those 
vertices. 
<H4>Street Race [IOI 95]</H4>
<P>Given: a directed graph, and a start point and an end point. 
<P>Find all points p that any path from the start point to the end must travel 
through p. 
<P>Analysis: The easiest algorithm is to remove each point in turn, and check to 
see if the end point is reachable from the start point. This runs in O(N (M + 
N)) time. Since the original problem stated that M &lt;= 100, and N &lt;= 50, 
this will run in time easily. 
<H4>Cow Tours [1999 USACO National Championship, abridged]</H4>
<P>The diameter of a connected graph is defined as the maximum distance between 
any two nodes of the graph, where the distance between two nodes is defined as 
the length of the shortest path. 
<P>Given a set of points in the plane, and the connections between those points, 
find the two points which are currently not in the same component, such that the 
diameter of the resulting component is minimized. 
<P>Analysis: Find the components of the original graph, using the method 
described above. Then, for each pair of points not in the same component, try 
placing a connection between them. Find the pair that minimizes the diameter. 
<H4>Connected Fields</H4>
<P>Farmer John contracted out the building of a new barn. Unfortunately, the 
builder mixed up the plans of Farmer John's barn with another set of plans. 
Farmer John's plans called for a barn that only had one room, but the building 
he got might have many rooms. Given a grid of the layout of the barn, tell 
Farmer John how many rooms it has. 
<P>Analysis: The graph here is on the non-wall grid locations, with edge between 
adjacent non-wall locations, although the graph should be stored as the grid, 
and not transformed into some other form, as the grid is so compact and easy to 
work with. <BR><BR>
<CENTER><A href="mailto:[e-mail]">Submit Solution via Email</A> 
&nbsp;|&nbsp; <A href="http://ace.delos.com/usacogate?a=mDx8aVs8FYS">USACO 
Gateway </A>&nbsp;| &nbsp; <A href="mailto:[e-mail]">Comment or 
Question </A></CENTER></BODY></HTML>