Easy to Understand (slow Python) Template for Problem: number of island and friend circle
| 1  | 0  | 0  | 1  |\n|---|---|---|---|\n|  0 | 1  | 1  | 0  |\n|  0 | 1  | 1  | 1  |\n| 1  | 0  | 1  | 1  |\nIf this example is for the problem number of isla
| 1  | 0  | 0  | 1  |\n|---|---|---|---|\n|  0 | 1  | 1  | 0  |\n|  0 | 1  | 1  | 1  |\n| 1  | 0  | 1  | 1  |\nIf this example is for the problem number of islands, the answer should be 4: (0, 0), (0, 3), (3, 0), (1, 1) four different starting nodes\n\nFor friend circle, (0, 3) or (3, 0) mean that 0-th and 3-th are friends! Take a moment and let that sink in!\nThis brings 4 isolated islands/friend circles into 1\n\nHow do we explore this kind of relationship?\n\nFor number of islands, we start with a square area in a grid marked as \'1\' then explore its close neighbors if there is. Assume that (i, j) is a grid marked as \'1\'. Then next we will explore its close neighbors: (i+1, j), (i-1, j), (i, j+1), (i, j-1)\n\nFor friend circles, starting point remains the same. The difference is how do you see its close neighbors?\nAssume that (i, j) is what we\'re inspecting now. Assume we stand on this tiny area. Look at your row direction to see if there is any one out there? If there is, he/she is your friend. Do the same for your column direction. \n\nNow, we could reason our neighbors to be explored:  we still explore our close neighbors: (i+1, j), (i-1, j), (i, j+1), (i, j-1). But on top of this, we want to explore the entire row and column as well. \n\nAlright. That\'s everything we need to know. Code it up.\n\nJust a tiny change of code and we can solve number of island problem.\n\n\n\n```\nclass Solution:\n    def findCircleNum(self, M: List[List[int]]) -> int:\n        \n        m = len(M)\n        n = len(M)\n        \n        def dfs(i, j):\n            if (i, j) in visited:\n                return\n                \n            visited.add((i, j))\n            \n            # NOTE: potential exploratory places.\n\t\t\t# This is the key differnce between the two problem: number of island and friend circle.\n\t\t\t# number of island: just pick the base\n\t\t\t# friend circle: pick all three (base, tmp1, tmp2)\n\t\t\t\n            base = [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]\n            tmp1 = [(i, j) for i in range(m)] # column-wise lookup\n            tmp2 = [(i, j) for j in range(n)] # row-wise lookup\n            \n            \n            for nodeIndex in base + tmp1 + tmp2:\n                if 0 <= nodeIndex[0] < m and 0 <= nodeIndex[1] < n:\n                    if nodeIndex not in visited and M[nodeIndex[0]][nodeIndex[1]] == 1:\n                        dfs(nodeIndex[0], nodeIndex[1])   \n                        \n        visited = set()\n        count = 0\n        for i in range(m):\n            for j in range(n):\n                if (i, j) not in visited and M[i][j] == 1:\n                    dfs(i, j)\n                    count += 1\n                    \n        return count\n#############################\nclass Solution:\n    def numIslands(self, grid: List[List[str]]) -> int:\n        M = grid\n        \n        m = len(M)\n        count = 0\n        \n        if m == 0:\n            return count\n        n = len(M[0])\n        \n        def dfs(i, j):\n            if (i, j) in visited:\n                return\n            \n            \n            visited.add((i, j))\n            \n            \n            # potential exploratory places\n            base = [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]\n            #tmp1 = [(i, j) for i in range(m)]\n            #tmp2 = [(i, j) for j in range(n)]\n            \n            \n            for (I, J) in base:\n                if 0 <= I < m and 0 <= J < n:\n                    if (I, J) not in visited and M[I][J] == \'1\':\n                        dfs(I, J)\n                        \n                        \n                        \n        visited = set()\n        for i in range(m):\n            for j in range(n):\n                if (i, j) not in visited and M[i][j] == \'1\':\n                    dfs(i, j)\n                    count += 1\n                    \n        return count\n```
[]