229 - Scanner

[liulike]

How to solve it ?
THX!

[liulike]

[howardcheng]

Is it true that one doesn't need to backtrack? i.e. if there is a scan line with imperfect information, then we can pick any cell and color it either way and still get a solution (assuming a solution exists). I believe I have a proof of this, but my program is giving me wrong answer. An assertion shows that there is at least one case has triggers this condition.

I don't know if my proof is wrong or my implementation is wrong...

[liulike]

Any one else?
Plz give me some hint?

Thank you all!

[Quantris]

howard, what exactly do you mean?

how are you checking for ambiguous cases (more than one solution)?

[howardcheng]

What I mean is this:

- if there is a scanline in which the number of black cells is the same as the number of cells in the line, then you can fill the whole line black

- similarly, if there is a scanline with no black cells then all cells are white

- every time we fill in some cells (black/white) we have to update the counts.

So we repeatedly look for scanlines which are either completely black or completely white (for the undetermined cells). My claim is that if there is some cell which has not been filled but there is no scanline with complete information, then coloring this cell either way will lead to a valid solution (assuming that there was a solution to begin with).

[Andrew Neitsch]

Do you know why it is a special corrector problem?

[howardcheng]

No idea.

[bors]

Hi!

I keep getting WA for this one.

My test input is currently :

Code: Select all

7
10 10 6 4 6 8 13 15 11 6
0 1 2 2 2 2 4 5 5 6 7 6 5 6 6 5 5 6 6 3 2 2 1 0
2 4 5 5 7 6 7 10 10 10 7 3 3 5 5
0 0 1 3 4 4 4 4 3 4 5 7 8 8 9 9 6 4 4 2 0 0 0 0
10 10 6 4 6 8 13 15 11 6
0 1 2 2 2 2 4 5 5 6 7 6 5 6 6 5 5 6 6 3 2 2 1 0
2 4 5 5 7 6 7 10 10 10 7 3 3 5 5
0 0 1 3 4 4 4 4 3 2 5 7 8 8 9 9 6 4 4 2 0 0 0 0
9 11 5 4 2 2 5 14 9 6
0 0 0 2 2 2 3 5 4 5 6 7 5 5 3 3 3 3 4 3 2 0 0 0
2 2 3 4 5 6 7 10 7 7 4 3 2 2 3
0 0 1 3 4 3 3 3 3 3 4 4 6 5 5 5 4 3 3 3 2 0 0 0
0 0 0 5 3 3 13 13 4 0
0 0 0 0 0 0 0 1 2 5 4 4 3 3 3 3 3 3 3 3 1 0 0 0 
0 2 3 3 3 3 3 3 3 3 5 5 3 2 0
0 0 0 2 3 2 2 2 3 2 3 3 4 3 3 5 4 0 0 0 0 0 0 0
0 13 2 11 4 4 11 2 13 0
0 0 1 2 2 2 3 4 4 4 4 4 4 4 4 4 4 3 2 2 2 1 0 0
0 8 2 6 4 4 4 4 4 4 4 6 2 8 0
0 0 1 2 2 2 3 4 4 4 4 4 4 4 4 4 4 3 2 2 2 1 0 0
3 9 10 7 9 13 11 8 4 1
0 1 1 2 2 3 3 5 6 5 3 7 8 7 4 4 3 3 3 3 2 0 0 0 
0 5 5 8 9 9 4 1 2 5 6 8 7 4 2
0 0 1 1 3 3 4 3 4 6 6 4 4 6 6 5 5 5 5 2 2 0 0 0 
2 7 9 8 9 6 4 11 8 2
0 1 1 2 1 2 5 6 6 6 4 1 2 5 8 6 3 1 1 1 2 1 1 0
1 6 8 6 4 4 6 5 5 4 3 3 5 4 2
0 1 2 2 1 2 2 4 5 6 6 6 6 6 4 4 1 1 2 1 2 1 1 0 

And my program outputs

Code: Select all

.##########....
.##########....
....######.....
......####.....
.......####..##
.......########
#####..########
###############
..#########..##
....######.....

...............
...............
...............
...............
...............
...............
...............
...............
...............
...............

...#########...
..###########..
.....#####.....
......####.....
.......#......#
.......#......#
##.....#.....##
##############.
..#########....
....######.....

...............
...............
...............
......#####....
.....#....##...
....#......##..
.#############.
.#############.
..##......##...
...............

...............
.#############.
.#...........#.
.#.#########.#.
.#.#.......#.#.
.#.#.......#.#.
.#.#########.#.
.#...........#.
.#############.
...............

.#...#.....#...
.######...###..
.######..####..
...###...####..
...###..######.
..#############
..#####..######
.#####.....###.
.#.###.........
....#..........

...............
...............
...............
...............
...............
...............
...............
...............
...............
...............

Could anyone check my output and give me some other input to try ?

Thanks in advance.

[sclo]

Remember that the input doesn't need to correspond to a valid scan. The sensor data could be too high or too low for any images found by backtracking.

Also, I've checked the judge that backtracking is absolutely needed, just computing without backtracking will not solve some inputs. A hybrid of backtracking and computing must be done. There are unambiguous cases that contains undetermined squares that can't be solved using Howard's method.

The output given above is CORRECT.

[brianfry713]

I solved it without backtracking.

Code: Select all

set all cells to unknown

do {
  for every scan line {
    count the number of unknown, blank, and filled cells
    if the count of filled cells equals the number of filled cells, then change unknown cells to blank
    if the count of unknown cells plus the count of filled cells equals the number of filled cells, then change unknown cells to filled
  }
} while(a cell was modified)

If any cells are unknown or any scan line's count of filled cells doesn't equal the number of filled cells, then print a blank grid, otherwise print the completed grid.

[pritorius]

Hi BrianFry,

Thanks for sketching out the algo. Will try it.