Modeling sandpiles is an interesting problem in statistical physics. When dropping a sand grain
on an existing pile, most of the time the grain will stick to it or a couple of grains will slide down.
Occasionally, however, adding one extra grain to a pile will lead to a huge avalanche of sand grains
falling down.
A simple way to model sandpiles is the Abelian Sandpile Model. In this simple model the sandpile
is described as a two-dimensional lattice with on each lattice site a height (the number of sand
grains on that lattice site). When an additional grain is dropped on a lattice site, its height is
increased by one. If the height becomes larger than a certain critical height, sand grains begin
to topple. This is modeled by reducing the number of sand grains on the site that is too high by
four, and increasing the heights of its four neighbors by one. If some of the neighbors exceed the
critical height after this toppling, sand grains topple from those points too until the situation is
stable again. If a sand grain falls off the lattice, the grain is gone.
Given an initial sandpile and the positions where the grains are dropped, determine the final
sandpile.
The first line of the input file contains a single number: the number of test cases to follow. Each
test case has the following format:
For every test case in the input file, the output should contain y lines, each with x characters in
the range '0'...'9': the heights of the final sandpile.
3 3 4 1 5 1023 2344 0000 2 3 3 4 1 4 1023 2344 0000 2 3 7 7 1 9 9999999 9999999 9999999 9999999 9999999 9999999 9999999 4 4
1023 2354 0000 1034 2421 0011 7999997 9799979 9979799 9996999 9979799 9799979 7999997
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|