PROB1: VACUUM INJECTION MODELING

Determine the time for filling a vacuum injection mold with resin.

INPUT: prob1.dat

The input file contains a sequence of models for rectangular resin molds, approximated as a matrix of cells which are either solid or void. Two cells serve the special purpose of the injection (source) point for the resin, and another is the drain (sink).

The number of rows and columns of cells in the mold is given before each mold in the input file, with row and column dimension of 0 denoting the end of the input file. Here are things you can count on for each mold:

Each mold is enclosed by solid (# symbols).

Each mold contains at least one void (blank), exactly one resin source (+) and exactly one resin sink (-).

All interior void cells are connected to the sink and source cells. That is, you may reach, through horizontal or vertical movements in void cells only, from any one void cell to either the source or sink.

No mold will consist of more than 100 horizonal or 100 vertical cells.

Here is an example input file representing two molds:

       column   111111111122222222223
       123456789012345678901234567890
line 1:10 21[EOL]
     2:#####################[EOL]
     3:#+                 -#[EOL]
     4:# ##### ##### #######[EOL]
     5:#    ##    ##       #[EOL]
     6:# ## ## ##### ## ## #[EOL]
     7:# ## ## ##### ## ## #[EOL]
     8:#    ## ##### ## ## #[EOL]
     9:# ## ## ##### ## ## #[EOL]
    10:# ## ##    ## ## ## #[EOL]
    11:#####################[EOL]
    12:3 5[EOL]
    13:#####[EOL]
    14:#+ -#[EOL]
    15:#####[EOL]
    16:0 0[EOL]
      :[EOF]

Here, column 20 of line 3 is a - (minus or hyphen) symbol. The [EOL] denotes the system end-of-line marker, and [EOF] denotes the end of the file.

MODEL

The discrete model for resin flow is the following:

(1)  On each discrete time step, enough resin is injected into the source (+) to fill a single cell.

(2)  At t=0, this completely fills the source cell with resin, and there is no overflow for the next time step.

(3)  For t=1 and later, things are a little more complicated:

(3.1)  The boundary cells are all the void cells which are adjacent (either vertically or horizontally) to completely filled cells, but which are not completely filled themselves. The sink (-) cell is always effectively empty. If the sink cell is adjacent to a full cell, then it will be a boundary cell.

(3.2)  Each cell on the boundary is filled by an equal fraction of the injected resin, plus any overflow from the previous injection: if there are N cells on the boundary, and A amount of overflow from the previous time step, then each is filled with (1+A)/N fraction of resin (in addition to whatever resin currently resided there)

(3.3)  Any cell, except the resin sink (-), which is filled to more than capacity by this step is instead filled exactly to capacity. Because of roundoff errors, consider "full" to be a fill ratio of greater than 0.999999. The overflow resin is added to what will be injected on the next time step.

(4)  After any time step, the sink cell (-) is empty, even though some resin may have flowed into it.

Here is pseudo-code for advancing the resin configuration for one generic time step. The overflow variable is considered to persist between steps, since it is the previously computed value (which should be initially zero) that is used to determine the amount of fill for this step.

subroutine move_forward_in_time
    determine number of boundary cells
    fill=(1+overflow)/number_of_boundary_cells
    overflow=0
    loop through all (i,j) which label boundary cells:
        fullness(i,j)=fullness(i,j) + fill
        if (fullness(i,j) > 0.999999) then
            overflow = overflow + (fullness(i,j)-1)
            fullness(i,j)=1
        end if
    end loop
    fullness(sink_i,sink_j)=0
end subroutine

Fullness(i,j) is the double precision floating point number representing the fill ratio (0 for empty, 1 for full) of the cell at row i and column j.

NUMERICAL ACCURACY NOTES

Do all floating-point computations using (at least) double precision arithmetic.

OUTPUT: prob1.out

For each of the mold representations in the input file, your program should determine how long (discrete time units) the injection should occur before the mold completely fills every void. These numbers should be printed on separate lines with no blanks.

The output file corresponding to the example input file should contain

       column   111111111122222222223
       123456789012345678901234567890
line 1:Program 1 by team 0[EOL]
     2:79[EOL]
     3:2[EOL]
     4:End of program 1 by team 0[EOL]
      :[EOF]