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

0 0 8 minutes read

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

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++

// C++ implementation of the approach
 
#include <bits/stdc++.h>
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<vector<bool> >& 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<pair<int, int> > moves)
{
    int x, y;
    vector<vector<bool> > 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<pair<int, int> > moves = { { 1, 1 },
                                      { 1, 2 },
                                      { 1, 3 } };
    int m = moves.size();
 
    cout << minimumMoveSquare(n, m, moves);
 
    return 0;
}

Python3

# Python3 implementation of the approach
 
# Function that returns True
# if the coordinate is inside the grid
def valid(x, y, n):
 
    if (x < 1 or y < 1 or x > n or 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
def count(n, cx, cy, board):
 
    ct = 0;
 
    # Iterate through 3 rows
    for x in range(cx, cx + 3):
 
        # Iterate through 3 columns
        for y in range(cy + 3):
 
            # 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
def minimumMoveSquare(n, m, moves):
 
    x = 0
    y = 0
    board=[[] for i in range(n + 1)]
 
    # Initialize all squares to be uncoloured
    for i in range(1, n + 1):
        board[i] = [False for i in range(n + 1)]
 
    for  i in range(len(moves)):
     
        x = moves[i][0];
        y = moves[i][1];
 
        # 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 cx in range(x - 2, x + 1 ):
            for cy in range(y - 2, y + 1):    
                if (count(n, cx, cy, board) == 9):
                    return i + 1;
    return -1;
 
# Driver code
if __name__=='__main__':
 
    n = 3;
    moves = [[ 1, 1 ],[ 1, 2 ], [ 1, 3 ]]
    m = len(moves)
 
    print(minimumMoveSquare(n, m, moves))
 
    # This code is contributed by rutvik_56.

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function that returns true
// if the coordinate is inside the grid
function valid(x, y, 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
function count(n, cx, cy, board)
{
    var ct = 0;
 
    // Iterate through 3 rows
    for (var x = cx; x <= cx + 2; x++)
 
        // Iterate through 3 columns
        for (var 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
function minimumMoveSquare(n, m, moves)
{
    var x, y;
    var board = Array.from(Array(n+1), ()=>Array(n+1).fill(false));
 
    for (var i = 0; i < moves.length; i++) {
        x = moves[i][0];
        y = moves[i][1];
 
        // 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 (var cx = x - 2; cx <= x; cx++)
            for (var cy = y - 2; cy <= y; cy++)
                if (count(n, cx, cy, board) == 9)
                    return i + 1;
    }
 
    return -1;
}
 
// Driver code
var n = 3;
var moves = [ [ 1, 1 ],
                                  [ 1, 2 ],
                                  [ 1, 3 ] ];
var m = moves.length;
document.write( minimumMoveSquare(n, m, moves));
 
// This code is contributed by famously.
</script>

Java

import java.util.*;
 
public class Main {
 
    // Function that returns True if the coordinate is inside the grid
    public static boolean 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
    public static int count(int n, int cx, int cy, boolean[][] board) {
        int ct = 0;
 
        // Iterate through 3 rows
        for (int x = cx; x < cx + 3; x++) {
 
            // Iterate through 3 columns
            for (int y = cy; y < cy + 3; y++) {
 
                // Check if the current square is valid and coloured
                if (valid(x, y, n)) {
                    if (board[x][y]) {
                        ct++;
                    }
                }
            }
        }
        return ct;
    }
 
    // Function that returns the query number after which the grid will
    // have a 3X3 coloured square
    public static int minimumMoveSquare(int n, int m, int[][] moves) {
        int x = 0, y = 0;
        boolean[][] board = new boolean[n + 1][n + 1];
 
        // Initialize all squares to be uncoloured
        for (int i = 1; i <= n; i++) {
            Arrays.fill(board[i], false);
        }
 
        for (int i = 0; i < m; i++) {
 
            x = moves[i][0];
            y = moves[i][1];
 
            // 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
    public static void main(String[] args) {
        int n = 3;
        int[][] moves = { { 1, 1 }, { 1, 2 }, { 1, 3 } };
        int m = moves.length;
 
        System.out.println(minimumMoveSquare(n, m, moves));
    }
}
 
// This code is contributed by Prince Kumar

C#

// C# porgrm for the above approach
 
using System;
public class Program
{
    // Function that returns True if the coordinate is inside the grid
    public static 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
    public static int Count(int n, int cx, int cy, bool[][] board)
    {
        int ct = 0;
 
        // Iterate through 3 rows
        for (int x = cx; x < cx + 3; x++)
        {
 
            // Iterate through 3 columns
            for (int y = cy; y < cy + 3; y++)
            {
 
                // Check if the current square is valid and coloured
                if (Valid(x, y, n))
                {
                    if (board[x][y])
                    {
                        ct++;
                    }
                }
            }
        }
        return ct;
    }
 
    // Function that returns the query number after which the grid will
    // have a 3X3 coloured square
    public static int MinimumMoveSquare(int n, int m, int[][] moves)
    {
        int x = 0, y = 0;
        bool[][] board = new bool[n + 1][];
 
        // Initialize all squares to be uncoloured
        for (int i = 1; i <= n; i++)
        {
            board[i] = new bool[n + 1];
            for (int j = 1; j <= n; j++)
            {
                board[i][j] = false;
            }
        }
 
        for (int i = 0; i < m; i++)
        {
 
            x = moves[i][0];
            y = moves[i][1];
 
            // 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
    public static void Main()
    {
        int n = 3;
        int[][] moves = new int[3][];
        moves[0] = new int[] { 1, 1 };
        moves[1] = new int[] { 1, 2 };
        moves[2] = new int[] { 1, 3 };
        int m = moves.Length;
 
        Console.WriteLine(MinimumMoveSquare(n, m, moves));
    }
}
 
// This code is contributed by adityasharmadev01

Output

-1

Time Complexity: O(m)

Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!