<p>Given an <code>n x n</code> binary matrix <code>grid</code>, return <em>the length of the shortest <strong>clear path</strong> in the matrix</em>. If there is no clear path, return <code>-1</code>.</p>

<p>A <strong>clear path</strong> in a binary matrix is a path from the <strong>top-left</strong> cell (i.e., <code>(0, 0)</code>) to the <strong>bottom-right</strong> cell (i.e., <code>(n - 1, n - 1)</code>) such that:</p>

<ul>
	<li>All the visited cells of the path are <code>0</code>.</li>
	<li>All the adjacent cells of the path are <strong>8-directionally</strong> connected (i.e., they are different and they share an edge or a corner).</li>
</ul>

<p>The <strong>length of a clear path</strong> is the number of visited cells of this path.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/example1_1.png" style="width: 500px; height: 234px;" />
<pre>
<strong>Input:</strong> grid = [[0,1],[1,0]]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/example2_1.png" style="height: 216px; width: 500px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,0],[1,1,0],[1,1,0]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0,0],[1,1,0],[1,1,0]]
<strong>Output:</strong> -1
</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 &lt;= 100</code></li>
	<li><code>grid[i][j] is 0 or 1</code></li>
</ul>

// class Solution {
// public:
//     std::vector<std::pair<int, int>>
//     find_viable_directions(vector<vector<int>>& grid, int x, int y) {
//         std::vector<std::pair<int, int>> directions = {
//             {1, 1},   {1, 0},  {1, -1}, {0, -1},
//             {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}};
//         std::vector<std::pair<int, int>> res;
//         for (const auto& dir : directions) {
//             int x_delta = dir.first;
//             int y_delta = dir.second;
//             if ((x + x_delta) < 0 || (x + x_delta) >= grid.size() ||
//                 (y + y_delta) < 0 || (y + y_delta) >= grid.size()) {
//                 continue;
//             }
//             if (grid[x + x_delta][y + y_delta] == 0) {
//                 res.push_back(dir);
//             }
//         }

//         return res;
//     }
//     int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
//         if (grid[0][0] == 1 || grid[grid.size() - 1][grid.size() - 1] == 1) {
//             return -1;
//         }
//         int cur_len = 1;
//         int path = 100 * 100 + 1;
//         std::queue<std::pair<int, int>> q;
//         q.push({0, 0});
//         while (!q.empty()) {
//             std::pair<int, int> cur_pos = q.front();
//             q.pop();
//             std::vector<std::pair<int, int>> viable_dirs =
//                 find_viable_directions(grid, cur_pos.first, cur_pos.second);
//             for (const auto& viable_dir : viable_dirs) {
//                 if (cur_pos.first + viable_dir.first == grid.size() - 1 &&
//                     cur_pos.second + viable_dir.second == grid.size() - 1) {
//                     path = min(path, cur_len + 1);
//                     continue;
//                 }
//                 grid[viable_dir.first][viable_dir.second] = cur_len + 1;
//                 q.push(viable_dir);
//             }
//             cur_len += 1;
//         }
//         return path;
//     }
// };


class Solution {
public:
    std::vector<std::pair<int, int>>
    find_viable_directions(const vector<vector<int>>& grid, int x, int y) {
        std::vector<std::pair<int, int>> directions = {
            {1, 1},   {1, 0},  {1, -1}, {0, -1},
            {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}};
        std::vector<std::pair<int, int>> res;
        int n = grid.size();
        for (const auto& dir : directions) {
            int new_x = x + dir.first;
            int new_y = y + dir.second;
            if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= n) {
                continue;
            }
            if (grid[new_x][new_y] == 0) {
                res.push_back({new_x, new_y});
            }
        }
        return res;
    }

    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
            return -1;
        }
        
        std::queue<std::pair<int, int>> q;
        q.push({0, 0});
        grid[0][0] = 1;  // Mark the start as visited
        
        int path_length = 0;
        while (!q.empty()) {
            int level_size = q.size();
            path_length++;
            
            for (int i = 0; i < level_size; i++) {
                auto [x, y] = q.front();
                q.pop();
                
                if (x == n - 1 && y == n - 1) {
                    return path_length;
                }
                
                std::vector<std::pair<int, int>> viable_dirs = find_viable_directions(grid, x, y);
                for (const auto& [new_x, new_y] : viable_dirs) {
                    grid[new_x][new_y] = 1;  // Mark as visited
                    q.push({new_x, new_y});
                }
            }
        }
        
        return -1;  // No path found
    }
};
49915