Connected-Cells.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import os\n",
    "import random\n",
    "import re\n",
    "import sys\n",
    "import collections\n",
    "\n",
    "\n",
    "def connectedCell(matrix):\n",
    "    max_region = 0\n",
    "    movement = [(0,1), (0,-1), (1,0), (-1,0), (-1,1), (-1,-1), (1,1), (1,-1)]\n",
    "    queue = collections.deque()\n",
    "    M = len(matrix)\n",
    "    N = len(matrix[0])\n",
    "    def bfs(queue, M, N):\n",
    "        curr_region = 1\n",
    "        while queue:\n",
    "            curr_row, curr_col = queue.popleft()\n",
    "            # print(\"Searching neighbors to cell: \", (curr_row, curr_col))\n",
    "            for (dx, dy) in movement:\n",
    "                new_row = curr_row + dx\n",
    "                new_col = curr_col + dy\n",
    "                if (0 <= new_row < M) and (0 <= new_col < N) and (matrix[new_row][new_col] == 1):\n",
    "                    matrix[new_row][new_col] = 2\n",
    "                    curr_region += 1\n",
    "                    queue.append((new_row, new_col))\n",
    "                    # print(\"queue: \", queue)\n",
    "        return curr_region\n",
    "    for row in range(M):\n",
    "        for col in range(N):\n",
    "            if matrix[row][col] == 1:\n",
    "                pos = (row,col)\n",
    "                # print(\"Found fill cell at: \", (row,col))\n",
    "                matrix[row][col] = 2\n",
    "                queue.append(pos)\n",
    "                curr_region = bfs(queue, M, N)\n",
    "                # print(\"Adjacent cells in region:\", curr_region)\n",
    "                max_region = max(curr_region, max_region)                \n",
    "    return max_region\n",
    "                \n",
    "if __name__ == '__main__':\n",
    "    fptr = open(os.environ['OUTPUT_PATH'], 'w')\n",
    "\n",
    "    n = int(input().strip())\n",
    "\n",
    "    m = int(input().strip())\n",
    "\n",
    "    matrix = []\n",
    "\n",
    "    for _ in range(n):\n",
    "        matrix.append(list(map(int, input().rstrip().split())))\n",
    "\n",
    "    result = connectedCell(matrix)\n",
    "\n",
    "    fptr.write(str(result) + '\\n')\n",
    "\n",
    "    fptr.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# PROBLEM: Print the number of adjacent cells in the biggest region\n",
    "# =========== MATRIX DIAGRAM ============ #\n",
    "#              REGION = 1 CELL\n",
    "#                ||\n",
    "#                V\n",
    "            #  0 1 0 0 1 0 1 1  <-- REGION = 2 CELLS     \n",
    "            #  0 0 1 1 1 0 0 0      \n",
    "            #  0 0 1 1 0 0 1 0\n",
    "            #  0 0 1 0 0 0 0 0\n",
    "            #  0 0 1 0 0 0 0 0\n",
    "            #      ^\n",
    "            #     ||          \n",
    "#              REGION = 9 CELLS\n",
    "# ==>  LARGEST REGION = 9 CELLS\n",
    "# ======================================== #\n",
    "\n",
    "# ==========  VARIABLES  =============== #\n",
    "# Max_Region = 0 --> Keeps track of largest amount of adjacent cells\n",
    "# Queue = [] --> Keeps track of cells to search\n",
    "# M = Length of Rows --> Use to iterate every row\n",
    "# N = Length of Columns --> Use to iterate every column\n",
    "\n",
    "#             Right   Left    Down    Up   UpRight   UpLeft  DownRight  DownLeft \n",
    "# Movement = [(0,1), (0,-1), (1,0), (-1,0), (-1,1), (-1,-1),  (1,1),    (1,-1)]\n",
    "# ======================================== #\n",
    "\n",
    "# STEP 1: Use a count to keep track of cells in max_region\n",
    "# STEP 2: Iterate every cell in the matrix to search for filled cells\n",
    "    # - Use a double-nested for loop to iterate each cell in matrix\n",
    "        # - Start at (0,0) in matrix \n",
    "        # - Search for filled cells\n",
    "        # - If we find a filled cell, then add the position(i,j) to queue\n",
    "        # >>> for row in range(M):\n",
    "        # >>>    for col in range(N):\n",
    "        # >>>        if matrix[row][col] == 1:\n",
    "        # >>>           queue.append(row,col) *Add position(row,col) to Queue*\n",
    "# STEP 3: Use Breadth-First Search to calculate number of adjacent components\n",
    "                        # Example: Position = (0,1)\n",
    "                                  # -> Matrix(0,1) = 1\n",
    "                                  # Add position(0,1) to Queue:                               \n",
    "                                    # Queue = [(0,1)]\n",
    "                                      # Mark Cell Value = 2\n",
    "                                            #  0 2 0 0 1 0 1 1\n",
    "                                            #  0 0 1 1 1 0 0 0      \n",
    "                                            #  0 0 1 1 0 0 1 0\n",
    "                                            #  0 0 1 0 0 0 0 0\n",
    "                                            #  0 0 1 0 0 0 0 0\n",
    "    # - Use the moves[] array to calculate 8 new positions at current position\n",
    "    # At each new position, check for the following criteria:\n",
    "    # (1) Cell Position is within Matrix Range\n",
    "        # >>> (0 <= new_row < M) and (0 <= new_col < N):\n",
    "    # (2) Cell is Filled \n",
    "        # Matrix[new_row, new_col] == 1:\n",
    "    # (*) If both conditions are satisfied:\n",
    "          # >>> increment curr_region by 1\n",
    "          # >>> mark cell = 2\n",
    "          # (*) Update max_region \n",
    "            # >>> if (curr_region > max_region): max_region = curr_region\n",
    "    # (*) If there aren't any more adjacent cells, then continue to iterate matrix \n",
    "    # (*) Return the max_region\n",
    "# INPUT: Matrix where each cell contains 0 or 1\n",
    "    # 1 -> FILLED CELL\n",
    "    # 0 -> UNFILLED CELL\n",
    "    # Cells are connected if they are adjacent in the following way:\n",
    "        # (*) Horizontally -> Example: 1 1 1   0 0 0\n",
    "        #                              0 0 0   1 1 1\n",
    "        #                              0 0 0   0 0 0\n",
    "\n",
    "        # (*) Vertically -> Example: 0 1 0    1 0 0\n",
    "        #                            0 1 0    1 0 0\n",
    "        #                            0 1 0    1 0 0\n",
    "        \n",
    "        # (*) Diagonally -> Example: 0 0 1    1 0 0\n",
    "        #                            0 1 0    0 1 0\n",
    "        #                            1 0 0    0 0 1\n",
    "\n",
    "# ======== BREADTH-FIRST SEARCH =========== #\n",
    "    # STEP 1: PICK A CELL IN MATRIX\n",
    "        # - VISIT THE UNVISITED ADJACENT CELLS \n",
    "        # - MARK ADJACENT CELLS AS VISITED\n",
    "        # - ADD CELL TO QUEUE\n",
    "    # STEP 2: IF THERE ARE NO MORE UNVISITED ADJACENT CELLS LEFT, REMOVE THE FIRST CELL FROM QUEUE\n",
    "    # STEP 3: REPEAT STEPS (1) AND (2) UNTIL THERE ARE NO MORE THE QUEUE IS EMPTY"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}