PROBLEM LINK:Practice Setter: Hasan Jaddouh DIFFICULTY:Simple PREREQUISITES:Basic Implementation. PROBLEM:Given a $N*M$ grid containing some obstacles represented by '#' and remaining empty cells represented by '.', Determine if it is possible to color only the empty cells if we can color a $2*2$ subrectangle in one move if it doesn't contain any obstacles. Note that we don't need to count the number of moves, just tell whether it is possible to color or not. SUPER QUICK EXPLANATION
EXPLANATIONLet's define a position $(i,j)$ valid, if all four positions $(i,j)$,$(i,j+1)$,$(i+1,j)$ and $(i+1,j+1)$ are empty positions, because we can apply the move here without coloring any obstacles. First of all, we find all the valid positions in the grid and store the result of applying move at that position. For this purpose, we can make an auxiliary grid, where we mark the positions which can be colored using operations at any valid position. Now, We know where the moves can be applied, so make another grid, and find out the final grid after applying all operations. Now, If all the empty cells from given grid are marked colored, then it is possible to color all empty cells without coloring any obstacles, so print Yes. Otherwise, print No. Related ProblemsThere are a lot of problems which involve grids which occurred recently, like AVGMAT, GRIDGM Also, Prefix/Suffix sums combined with grid or even 3dimensional arrays form interesting problems, and thus, are a nice topic for practice. Another Interesting grid problem involves dynamicprogramming on grids depending upon some conditions, which you may find here. Time ComplexityTime complexity is $O(N*M)$ per test case. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 26 Oct '18, 13:55

Want to share some learning after this problem. Approach :Brute force approach works well for this problem. Just check all possible 2 X 2 subarrays and if it is safe ( no #) in them, just fill color ( can be done by taking another array bool coloured[n][m] and mark it true). Then check if all empty cells of given array (a[i][j] = '.') are coloured or not. Difference between TLE and AC.Tried first time using map of pair of i,j to coloured ( map < pair <int,int> , int >) and got TLE (now I think why I took map in first place) Just switched to an array to store coloured status (bool coloured [n][m]) and got AC. LearningKeep it simple (stick to basics: access time of arrays ( O(1) ) is faster than map (logarithmic) ) Here is the code for one test case answered 28 Oct '18, 13:19

Another very similar problem https://codeforces.com/problemset/problem/1059/B :) The basic way to solve is same for all possible cells, what cells you can visit without visiting any unwanted cell and in the end verify that all required cells are visited at least once. answered 27 Oct '18, 22:57

I was annoyed with myself for trying to do evaluation of different geometry of obstacles (which failed) instead of just colouring the grid, which works fine (but which I implemented just too late, having started late on the contest). answered 27 Oct '18, 23:50
1
Oh. It was just a simple implementation.
(27 Oct '18, 23:58)
Yes  my geometryanalysis evaluation was more complicated, taking a lot of thinking time, and the reason it didn't work was because I somehow had got the idea that the obstacles were sparse, which of course is not necessarily the case.
(28 Oct '18, 00:10)

What's wrong in going with approach with checking where '#' is there and from there just check if all other possible cells i.e. (i+1,j), (i+2,j),(i,j+1),(i,j+2) are possible to fill or not, if it's possible to fill then there is no problem with this '#' move to next.
Please point out my mistake
answered 28 Oct '18, 00:14

The question is easy still ,I am stuck . Can someone please point out what's wrong with my code ? link : https://www.codechef.com/viewsolution/21248302 answered 28 Oct '18, 00:55

Can someone please help me point out where am I wrong? answered 28 Oct '18, 01:44

Could someone point out the flaw here?Worked for 2 out of 3 subtasks. answered 28 Oct '18, 13:05

Please tell the problem with this code, concept used: not possible iff there is a single '.' in any row or column(like .# at start, #. at end or #.# in between) answered 28 Oct '18, 17:36

it's always good to see @Taranpreet Singh's editorial :) answered 29 Oct '18, 00:14

i tried checking if i can find a '.' in between 2 '#' for this i just added '#' all around my grid so if anywhere in my initial grid i find '#' i will search if i m having a '.' adjacent to it in all the directions and a '#' at position adjacent to the '.' if i find any such case i will return NO. and if i dont find any such case its YES. its almost same as sachit777's soution which you have replied but i am checking the top and bottom as well and the case which you give him is working with my algo but last case is giving WA while submitting. what could be the issue? answered 29 Oct '18, 19:47

@white_shadow_ i also implemented same logic during contest but got WA on subtask 2 . i also wonder what could be the the case here is my sol.https://www.codechef.com/viewsolution/21245085 answered 29 Oct '18, 22:44

I'm checking following conditions:
I'm getting WA on subtask 2 (similar to @white_shadow and @knakul853). Can anyone help with the case I'm not considering in my solution? https://www.codechef.com/viewsolution/21353530 answered 01 Nov '18, 07:57
Have you considered variations on this case:
(02 Nov '18, 05:51)

Why is this solution giving a TLE ? https://www.codechef.com/viewsolution/21622000 answered 14 Nov '18, 12:53

Being new to competitive programming my bigggest hint was that bruteforce is acceptable... i just checked all possible 2x2 grids......instead of using another array for storing result i just replaced every '.' in favourable grid with a '1'......then at last again i traversed the full grid to find if i encounter any '.' if i do then "NO" else "YES"..... have a look....its very simple.... =============MY CODE====================== https://www.codechef.com/viewsolution/22081531 answered 25 Dec '18, 13:06

HERE is my solution.. again matches with setter XDDD
plagiarism with all setter's XD