stould's blog

By stould, history, 8 years ago, In English

Hello Codeforces community!!

I'll be straight in this topic. I'm trying to solve the problem Nurikabe. But receiving TLE. If helps, the code.

I'm using a bruteforce solution, first of all, I am generating all fixed Polyominoes from size 1 to 9. So, now for each given grid, I do the following things:

  • 1) Storing all interesting points (points with numbers on the grid) in a vector<pair<int, int> > p.
  • 2) Now, I bruteforce with backtracking:
  • 2.1) If(all interesting points already have a polyminoes assiated) check if the actual grid is valid (according to statement) with a DFS // O(n*m)
  • 2.2) Te next step, I'll try to explain with a example:

supposing the bellow grid and a polyomino ###:

.....
..3..
.....

There are three possible ways to place this polyomino:

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

My algorithm follows the above example, for each polyomino[i] (with size equals to interesting point[i]), I try to place the polyomino fixing a cell.

  • 2.3) I check if is valid to use this polimino. //O(polyomino size)
  • 2.4) If is valid, add the polyomino on the grid //O(polyomino size)
  • 2.5) Try the next interesting point
  • 2.6) Remove the polymino from the grid. //O(polyomino size)

Does someone know some prunning to do in this backtracking to avoid TLE or is it a wrong approach ? Any help will be very apreciated, thank you.

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Hello, I want to revive this topic, because this problem is very interesting. Thanks in advance to any help.