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.