<p>Given an <code>n x n</code> <code>grid</code>&nbsp;containing only values <code>0</code> and <code>1</code>, where&nbsp;<code>0</code> represents water&nbsp;and <code>1</code> represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance.&nbsp;If no land or water exists in the grid, return <code>-1</code>.</p>

<p>The distance used in this problem is the Manhattan distance:&nbsp;the distance between two cells <code>(x0, y0)</code> and <code>(x1, y1)</code> is <code>|x0 - x1| + |y0 - y1|</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/05/03/1336_ex1.JPG" style="width: 185px; height: 87px;" />
<pre>
<strong>Input:</strong> grid = [[1,0,1],[0,0,0],[1,0,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The cell (1, 1) is as far as possible from all the land with distance 2.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/05/03/1336_ex2.JPG" style="width: 184px; height: 87px;" />
<pre>
<strong>Input:</strong> grid = [[1,0,0],[0,0,0],[0,0,0]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The cell (2, 2) is as far as possible from all the land with distance 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n&nbsp;&lt;= 100</code></li>
	<li><code>grid[i][j]</code>&nbsp;is <code>0</code> or <code>1</code></li>
</ul>

class Solution:
    def visitAll(self, grid, visited, i, j):
        if grid[i][j] == 1:
            return 1

        visited[i][j] = 1
        l = 0
        n_smallest = None
        c = []
        c_n = []
        neighbors = [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]
        for n in neighbors:
            n_i = n[0]
            n_j = n[1]
            print("NEIGHTHBORPIU0")
            print(n_i)
            print(n_j)
            if n_i >=0 and n_i < len(grid) and n_j >= 0 and n_j < len(grid[0]):
                if not visited[n_i][n_j]:
                    print("INSIDE")
                    print(n_i)
                    print(n_j)
                    c_n.append([n_i, n_j])
                    n_res = self.visitAll(grid, visited, n_i, n_j)
                    
                    if n_res == 0:
                        continue
                    # print("NRES NOT ZERO")
                    # print(n_res)
                    # print(n_smallest)
                    c.append(n_res)
                    if n_smallest is None:
                        # print("SETTING NSMALLEST 1")
                        # print(n_res)
                        n_smallest = n_res
                    elif n_res < n_smallest:
                        # print("SETTING NSMALLEST 2")
                        # print(n_res)
                        n_smallest = n_res
        
        if n_smallest is not None:
            l = n_smallest + 1
        print("RETURNING")
        print(c)
        print(c_n)
        print(i)
        print(j)
        return l

    # def fill(self, grid, found, i, j, count):
    #     found[i][j] = count
    #     if grid[i][j] == 0:
    #         continue
    #     neighbors = [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]
    #     for n in neighbors:
    #         n_i = n[0]
    #         n_j = n[1]
    #         if n_i >=0 and n_i < len(grid) and n_j >= 0 and n_j < len(grid[0]):
    #             if grid[n_i][n_j] == 1:
    #                 continue
    #             if not found[n_i][n_j]:
    #                 self.fill(grid, found, n_i, n_j, count+1)
    #                 # found[n_i][n_j] = count

    def maxDistance(self, grid: List[List[int]]) -> int:
        # found = [[0 for x in range(len(grid[0]))] for y in range(len(grid))]
        found = [[-1 for x in range(len(grid[0]))] for y in range(len(grid))]
        queue = []
        queue_level = []
        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):
                if grid[i][j] == 1:
                    queue.append([i, j])
                    queue_level.append(0)
                    found[i][j] = 0
            
                # if grid[i][j] == 0:
                #     continue
                # neighbors = [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]
                # for n in neighbors:
                #     n_i = n[0]
                #     n_j = n[1]
                #     if n_i >=0 and n_i < len(grid) and n_j >= 0 and n_j < len(grid[0]):
                #         if grid[n_i][n_j] == 1:
                #             continue
                #         if not found[n_i][n_j]:
                #             found[n_i][n_j] = count
        
        
        final_count = -1
        while queue:
            next_cell = queue.pop(0)
            count = queue_level.pop(0)
            if count != 0:
                final_count = count
            i = next_cell[0]
            j = next_cell[1]
            found[i][j] = count
            neighbors = [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]
            for n in neighbors:
                n_i = n[0]
                n_j = n[1]
                if n_i >=0 and n_i < len(grid) and n_j >= 0 and n_j < len(grid[0]):
                    if found[n_i][n_j] != -1:
                        continue
                    queue.append([n_i, n_j])
                    queue_level.append(count+1)
                    found[n_i][n_j] = 0
                    # if grid[n_i][n_j] == 1:
                    #     continue
                    # if not found[n_i][n_j]:
                    #     found[n_i][n_j] = count
        
        return final_count
                
        #         l = -1
        #         contenders = []
        #         while q:
        #             n_level = q.pop(0)
        #             l += 1
        #             for nn in n_level:
        #                 b_i = nn[0]
        #                 b_j = nn[1]
        #                 if grid[b_i][b_j] == 1:
        #                     if i == 0 and j == 1:
        #                         print("BREAK")
        #                     break

        #                 visited[b_i][b_j] = -1
        #                 neighbors = [[b_i+1, b_j], [b_i-1, b_j], [b_i, b_j+1], [b_i, b_j-1]]


        # res = -1
        # found = [[0 for x in range(len(grid[0]))] for y in range(len(grid))]
        # for i in range(0, len(grid)):
        #     for j in range(0, len(grid[0])):
        #         visited = [[0 for x in range(len(grid[0]))] for y in range(len(grid))]
        #         if grid[i][j] == 1:
        #             continue
        #         # if not visited[i][j]:
        #         l = self.visitAll(grid, visited, i, j)
                
        #         l = l - 1
        #         print("ENDD")
        #         print(l)
        #         print(i)
        #         print(j)
        #         # if i ==1 and j ==1:
        #         #     print(l)
        #         if res != 0 and l > res:
        #             res = l


        #         q = []
        #         visited = [[0 for x in range(len(grid[0]))] for y in range(len(grid))]
        #         q.append([[i, j]])
                
        #         l = -1
        #         contenders = []
        #         while q:
        #             n_level = q.pop(0)
        #             l += 1
        #             for nn in n_level:
        #                 b_i = nn[0]
        #                 b_j = nn[1]
        #                 if grid[b_i][b_j] == 1:
        #                     if i == 0 and j == 1:
        #                         print("BREAK")
        #                     break

        #                 visited[b_i][b_j] = -1
        #                 neighbors = [[b_i+1, b_j], [b_i-1, b_j], [b_i, b_j+1], [b_i, b_j-1]]
        #                 proceed = False
        #                 levelset = []
        #                 for n in neighbors:
        #                     n_i = n[0]
        #                     n_j = n[1]
        #                     if n_i >=0 and n_i < len(grid) and n_j >= 0 and n_j < len(grid[0]):
        #                         # if found[n_i][n_j] > 0:
        #                         #     contenders.append(l + found[n_i][n_j])
        #                         #     continue
        #                         if not visited[n_i][n_j]:
        #                             proceed = True
        #                             levelset.append([n_i, n_j])
        #                             continue
        #                 if levelset:
        #                     q.append(levelset)
        #                     if i == 0 and j == 1:
        #                         print("PRCEED")
                    
            
        #         # if contenders:
        #         #     m = min(contenders)
        #         #     l = l if l < m else m
        #         found[i][j] = l
        #         if i == 0 and j == 1:
        #             print("WTFFF")
        #             print(found)
        #             print(l)
        #         if l != 0 and l > res:
        #             res = l

        #         # if not visited[i][j]:
        #         #     l = self.visitAll(grid, visited, i, j)
        #         #     if res != 0 and l > res:
        #         #         res = l
        # print(found)

        # return res

623