<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 {
public:
    int maxDistance(vector<vector<int>>& grid)
    {
        int dirs[4][2] = { { -1,  0 }, {  0,  1 },
                           {  1,  0 }, {  0, -1 } };
        queue<pair<int, int>> *q;
        int i, i1, j, j1, k, n, *p, r, u, v, * *w;
        bool * *g;

        n = grid.size();
        q = new queue<pair<int, int>>();
        w = new int *[n];
        g = new bool *[n];
        for (i = 0; i < n; i++) {
            w[i] = new int[n];
            std::fill(&w[i][0], &w[i][n], n * 2 + 1);
            g[i] = new bool[n];
        }
        r = 0;
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                if (grid[i][j] != 0) {
                    w[i][j] = 0;
                    r++;
                }
        if (r > 0 && r < n * n) {
            for (i1 = 0; i1 < n; i1++) {
                for (j1 = 0; j1 < n; j1++)
                    if (grid[i1][j1] != 0) {
                        for (k = 0; k < n; k++)
                            std::fill(&g[k][0], &g[k][n], false);
                        q->push({ i1, j1 });
                        while (!q->empty()) {
                            tie(i, j) = q->front();
                            q->pop();
                            for (k = 0; k < 4; k++) {
                                u = i + dirs[k][0];
                                v = j + dirs[k][1];
                                if (u >= 0 && u < n && v >= 0 && v < n &&
                                    grid[u][v] == 0 && !g[u][v] &&
                                    w[u][v] > w[i][j] + 1) {
                                    w[u][v] = w[i][j] + 1;
                                    g[u][v] = true;
                                    q->push({ u, v });
                                }
                            }
                        }
                    }
            }
            r = 0;
            for (i = 0; i < n; i++) {
                for (j = 0; j < n; j++)
                    if (w[i][j] == n * 2 + 1)
                        w[i][j] = -1;
                p = std::max_element(&w[i][0], &w[i][n]);
                if (r < *p)
                    r = *p;
                delete[] g[i];
                delete[] w[i];
            }
        } else
            r = -1;
        
        delete[] g;
        delete[] w;
        delete q;

        return r;
    }
};
39106