# Minimum number of moves after which there exists a 3X3 coloured square

Given an N * N board which is initially empty and a sequence of queries, each query consists of two integers X and Y where the cell (X, Y) is painted. The task is to print the number of the query after which there will be a 3 * 3 square in the board with all the cells painted.

If there is no such square after processing all of the queries then print -1.

Examples:

Input: N = 4, q = {{1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {1, 4}, {2, 4}, {3, 4}, {3, 2}, {3, 3}, {4, 1}}
Output: 10
After the 10th move, there exists a 3X3 square, from (1, 1) to (3, 3) (1-based indexing).

Input: N = 3, q = {(1, 1), {1, 2}, {1, 3}}
Output: -1

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: An important observation here is that every time we colour a square, it can be a part of the required square in 9 different ways (any cell of the 3 * 3 square) . For every possibility, check whether the current cell is a part of any square where all the 9 cells are painted. If the condition is satisfied print the number of queries processed so far else print -1 after all the queries have been processed.

Below is the implementation of the above approach:

 `// C++ implementation of the approach ` ` `  `#include ` `using` `namespace` `std; ` ` `  `// Function that returns true ` `// if the coordinate is inside the grid ` `bool` `valid(``int` `x, ``int` `y, ``int` `n) ` `{ ` `    ``if` `(x < 1 || y < 1 || x > n || y > n) ` `        ``return` `false``; ` `    ``return` `true``; ` `} ` ` `  `// Function that returns the count of squares ` `// that are coloured in the 3X3 square ` `// with (cx, cy) being the top left corner ` `int` `count(``int` `n, ``int` `cx, ``int` `cy, ` `          ``vector >& board) ` `{ ` `    ``int` `ct = 0; ` ` `  `    ``// Iterate through 3 rows ` `    ``for` `(``int` `x = cx; x <= cx + 2; x++) ` ` `  `        ``// Iterate through 3 columns ` `        ``for` `(``int` `y = cy; y <= cy + 2; y++) ` ` `  `            ``// Check if the current square ` `            ``// is valid and coloured ` `            ``if` `(valid(x, y, n)) ` `                ``ct += board[x][y]; ` `    ``return` `ct; ` `} ` ` `  `// Function that returns the query ` `// number after which the grid will ` `// have a 3X3 coloured square ` `int` `minimumMoveSquare(``int` `n, ``int` `m, ` `                      ``vector > moves) ` `{ ` `    ``int` `x, y; ` `    ``vector > board(n + 1); ` ` `  `    ``// Initialize all squares to be uncoloured ` `    ``for` `(``int` `i = 1; i <= n; i++) ` `        ``board[i].resize(n + 1, ``false``); ` `    ``for` `(``int` `i = 0; i < moves.size(); i++) { ` `        ``x = moves[i].first; ` `        ``y = moves[i].second; ` ` `  `        ``// Mark the current square as coloured ` `        ``board[x][y] = ``true``; ` ` `  `        ``// Check if any of the 3X3 squares ` `        ``// which contains the current square ` `        ``// is fully coloured ` `        ``for` `(``int` `cx = x - 2; cx <= x; cx++) ` `            ``for` `(``int` `cy = y - 2; cy <= y; cy++) ` `                ``if` `(count(n, cx, cy, board) == 9) ` `                    ``return` `i + 1; ` `    ``} ` ` `  `    ``return` `-1; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `n = 3; ` `    ``vector > moves = { { 1, 1 }, ` `                                      ``{ 1, 2 }, ` `                                      ``{ 1, 3 } }; ` `    ``int` `m = moves.size(); ` ` `  `    ``cout << minimumMoveSquare(n, m, moves); ` ` `  `    ``return` `0; ` `} `

Output:

```-1
```

My Personal Notes arrow_drop_up Check out this Author's contributed articles.

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the "Improve Article" button below.

Article Tags :
Practice Tags :

Be the First to upvote.

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.
{"ft_lang_label":"__label__en","ft_lang_prob":0.7791063,"math_prob":0.98588836,"size":4077,"snap":"2020-10-2020-16","text_gpt3_token_len":1205,"char_repetition_ratio":0.13012521,"word_repetition_ratio":0.03685504,"special_character_ratio":0.31910717,"punctuation_ratio":0.14336075,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99732524,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-02-24T03:31:49Z\",\"WARC-Record-ID\":\"<urn:uuid:579f433d-d64e-429d-b1a2-a357009d3313>\",\"Content-Length\":\"140026\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:e28a5e8a-84d8-4e95-96c5-ee298f239d8c>\",\"WARC-Concurrent-To\":\"<urn:uuid:2e5939a9-e0c1-498a-ba35-f27ff6db9021>\",\"WARC-IP-Address\":\"204.237.142.232\",\"WARC-Target-URI\":\"https://www.geeksforgeeks.org/minimum-number-of-moves-after-which-there-exists-a-3x3-coloured-square/\",\"WARC-Payload-Digest\":\"sha1:5OYJ2TAWST562N6HXPDNTFYBH5NWAO3X\",\"WARC-Block-Digest\":\"sha1:MNWFFZVILAWGQ3CWIIEIAWZ4GE77USFE\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-10/CC-MAIN-2020-10_segments_1581875145869.83_warc_CC-MAIN-20200224010150-20200224040150-00379.warc.gz\"}"}