Fast Python solution using Depth-First Search
I hope you all enjoyed the contest this evening! I really liked this question, so I figured I\'d share my solution.\n\nThe grid is very hard to deal with by its
I hope you all enjoyed the contest this evening! I really liked this question, so I figured I\'d share my solution.\n\nThe grid is very hard to deal with by itself since it isn\'t spaced very well. So, let\'s increase the scale and represent walls (slashes) with 1 and empty spaces with 0. Here\'s what [" /", "/ "] looks like with scale 2:\n0 0 0 1\n0 0 1 0\n0 1 0 0\n1 0 0 0\n\nHm. This is good, but what if we have ["//", "/ "]?\n0 1 0 1\n1 0 1 0\n0 1 0 0\n1 0 0 0\n\nThose 3 right-diagonal 0\'s between the two slashes are bothersome. If we blow up the scale by 3x instead of just 2x, it looks like this:\n0 0 1 0 0 1\n0 1 0 0 1 0\n1 0 0 1 0 0\n0 0 1 0 0 0\n0 1 0 0 0 0\n1 0 0 0 0 0\n\nThat\'s much better - now we can represent partitioned areas as contiguous \'blobs\' of zeroes! Does this remind you of any other problems? It\'s reducible to "Number of Islands" - just count the islands of 0\'s.\n\nMy code isn\'t too pretty, but I hope this explanation helped. Feedback is appreciated. Here it is:\n\n```\n\t\tN = len(grid)\n        board = [[0 for j in range(3*N)] for i in range(3*N)]\n        \n        for i,row in enumerate(grid):\n            for j,cell in enumerate(row):\n                if cell == \'/\':\n                    board[3*i][3*j+2] = 1\n                    board[3*i+1][3*j+1] = 1\n                    board[3*i+2][3*j] = 1\n                elif cell == \'\\\\\':\n                    board[3*i][3*j] = 1\n                    board[3*i+1][3*j+1] = 1\n                    board[3*i+2][3*j+2] = 1\n        \n        zeroes = []\n        for i,row in enumerate(board):\n            for j,cell in enumerate(row):\n                if cell == 0:\n                    zeroes.append((i, j))\n        \n        seen = set()\n        ret = 0\n        for zero in zeroes:\n            if zero in seen:\n                continue\n            ret += 1\n            \n            dfs = [zero]\n            while dfs:\n                cur = dfs.pop()\n                if cur in seen:\n                    continue\n                \n                seen.add(cur)\n                i = cur[0]\n                j = cur[1]\n                \n                if i and board[i-1][j] == 0:\n                    dfs.append((i-1, j))\n                if j and board[i][j-1] == 0:\n                    dfs.append((i, j-1))\n                if i != 3*N-1 and board[i+1][j] == 0:\n                    dfs.append((i+1, j))\n                if j != 3*N-1 and board[i][j+1] == 0:\n                    dfs.append((i, j+1))\n        \n        return ret
[]