Hi all,
I need your help to solve
this problem (task mines day 2 Baltic OI 2010). I heard that it can be solved using Gaussian Elimination (but I haven't had detail ideas). According to what I know, Gaussian Elimination runs in O(N^3) and the space is O(N^2). I tried to transform this problem to gaussian elimination version. I ended up with this transformation:
1. Now define (x,y) into a number (we number every cells start from 1 to N*M)
2. Build N*M equations and save it in gaussian table. So table[i][j] has value 1 if node i and j are adjacent, otherwise 0
3. Input[i][j] (the given input) means how many bombs in cell(i,j) then table[transform(i,j)][N*M+1]=Input[i][j]
4. Solve it using gaussian elimination.
Unfortunately, for above-mentioned solution, I need O((N*M)^2) space and O((N*M)^3) time which is far enough to solve this problem. Any helps and ideas are appreciated. Thank you for your attention.
I am looking forward for a reply.
Полный текст и комментарии »