leetcode529

public class Solution {
    //DFS
        public char[,] UpdateBoard(char[,] board, int[] click)
        {
            int m = board.GetLength(0), n = board.GetLength(1);
            int row = click[0], col = click[1];

            if (board[row, col] == 'M')
            { // Mine
                board[row, col] = 'X';
            }
            else
            { // Empty
                // Get number of mines first.
                int count = 0;
                for (int i = -1; i < 2; i++)
                {
                    for (int j = -1; j < 2; j++)
                    {
                        if (i == 0 && j == 0) continue;
                        int r = row + i, c = col + j;
                        if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
                        if (board[r, c] == 'M' || board[r, c] == 'X') count++;
                    }
                }

                if (count > 0)
                { // If it is not a 'B', stop further DFS.
                    board[row, col] = (char)(count + '0');
                }
                else
                { // Continue DFS to adjacent cells.
                    board[row, col] = 'B';
                    for (int i = -1; i < 2; i++)
                    {
                        for (int j = -1; j < 2; j++)
                        {
                            if (i == 0 && j == 0) continue;
                            int r = row + i, c = col + j;
                            if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
                            if (board[r, c] == 'E') UpdateBoard(board, new int[] { r, c });
                        }
                    }
                }
            }
            return board;
        }

        ////BFS
        //public char[,] UpdateBoard(char[,] board, int[] click)
        //{
        //    int m = board.GetLength(0), n = board.GetLength(1);
        //    Queue<int[]> queue = new Queue<int[]>();
        //    queue.Enqueue(click);

        //    while (queue.Count > 0)
        //    {
        //        int[] cell = queue.Dequeue();
        //        int row = cell[0], col = cell[1];

        //        if (board[row, col] == 'M')
        //        { // Mine
        //            board[row, col] = 'X';
        //        }
        //        else
        //        { // Empty
        //            // Get number of mines first.
        //            int count = 0;
        //            for (int i = -1; i < 2; i++)
        //            {
        //                for (int j = -1; j < 2; j++)
        //                {
        //                    if (i == 0 && j == 0) continue;
        //                    int r = row + i, c = col + j;
        //                    if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
        //                    if (board[r, c] == 'M' || board[r, c] == 'X') count++;
        //                }
        //            }

        //            if (count > 0)
        //            { // If it is not a 'B', stop further DFS.
        //                board[row, col] = (char)(count + '0');
        //            }
        //            else
        //            { // Continue BFS to adjacent cells.
        //                board[row, col] = 'B';
        //                for (int i = -1; i < 2; i++)
        //                {
        //                    for (int j = -1; j < 2; j++)
        //                    {
        //                        if (i == 0 && j == 0) continue;
        //                        int r = row + i, c = col + j;
        //                        if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
        //                        if (board[r, c] == 'E')
        //                        {
        //                            queue.Enqueue(new int[] { r, c });
        //                            board[r, c] = 'B'; // Avoid to be added again.
        //                        }
        //                    }
        //                }
        //            }
        //        }
        //    }
        //    return board;
        //}
}

https://leetcode.com/problems/minesweeper/#/description

提供一种会超时的解决方案：

public char[,] UpdateBoard(char[,] board, int[] click)
        {
            var row = board.GetLength(0);//行数
            var col = board.GetLength(1);//列数

            var visited = new bool[row, col];//默认为全为false            

            var i = click[0];
            var j = click[1];
            if (board[i, j] == 'M')
            {
                board[i, j] = 'X';
                return board;
            }
            else
            {
                Queue<int[]> Q = new Queue<int[]>();
                var coord = new int[] { i, j };
                Q.Enqueue(coord);
                var list = new List<int[]>();//存储有效节点 
                while (Q.Any())
                {
                    var position = Q.Dequeue();
                    //获取新的坐标
                    var x = position[0];
                    var y = position[1];
                    visited[x, y] = true;//当前点被访问

                    //根据毗邻元素更新当前地板的标记
                    var minecount = 0;//八个方向毗邻地板的地雷个数
                    list.Clear();
                    //左上
                    var left_top = new int[] { x - 1, y - 1 };
                    if (left_top[0] >= 0 && left_top[1] >= 0 && !visited[left_top[0], left_top[1]])
                    {
                        if (board[left_top[0], left_top[1]] == 'M')
                        {
                            minecount++;//探测得一枚地雷
                        }
                        else
                        {
                            list.Add(left_top);//暂存有效节点
                        }
                    }

                    //正上
                    var top = new int[] { x - 1, y };
                    if (top[0] >= 0 && !visited[top[0], top[1]])
                    {
                        if (board[x - 1, y] == 'M')
                        {
                            minecount++;
                        }
                        else
                        {
                            list.Add(top);
                        }
                    }

                    //右上
                    var right_top = new int[] { x - 1, y + 1 };
                    if (right_top[0] >= 0 && right_top[1] <= col - 1 && !visited[right_top[0], right_top[1]])
                    {
                        if (board[right_top[0], right_top[1]] == 'M')
                        {
                            minecount++;
                        }
                        else
                        {
                            list.Add(right_top);
                        }
                    }

                    //正右
                    var right = new int[] { x, y + 1 };
                    if (right[1] <= col - 1 && !visited[right[0], right[1]])
                    {
                        if (board[right[0], right[1]] == 'M')
                        {
                            minecount++;
                        }
                        else
                        {
                            list.Add(right);
                        }
                    }

                    //右下
                    var right_bottom = new int[] { x + 1, y + 1 };
                    if (right_bottom[0] <= row - 1 && right_bottom[1] <= col - 1 && !visited[right_bottom[0], right_bottom[1]])
                    {
                        if (board[right_bottom[0], right_bottom[1]] == 'M')
                        {
                            minecount++;
                        }
                        else
                        {
                            list.Add(right_bottom);
                        }
                    }

                    //正下
                    var bottom = new int[] { x + 1, y };
                    if (bottom[0] <= row - 1 && !visited[bottom[0], bottom[1]])
                    {
                        if (board[bottom[0], bottom[1]] == 'M')
                        {
                            minecount++;
                        }
                        else
                        {
                            list.Add(bottom);
                        }
                    }

                    //左下
                    var left_bottom = new int[] { x + 1, y - 1 };
                    if (left_bottom[0] <= row - 1 && left_bottom[1] >= 0 && !visited[left_bottom[0], left_bottom[1]])
                    {
                        if (board[left_bottom[0], left_bottom[1]] == 'M')
                        {
                            minecount++;
                        }
                        else
                        {
                            list.Add(left_bottom);
                        }
                    }

                    //正左                               
                    var left = new int[] { x, y - 1 };
                    if (left[1] >= 0 && !visited[left[0], left[1]])
                    {
                        if (board[left[0], left[1]] == 'M')
                        {
                            minecount++;
                        }
                        else
                        {
                            list.Add(left);
                        }
                    }

                    //毗邻的八个位置都没有地雷
                    if (minecount == 0)
                    {
                        //当前节点标记为B
                        board[x, y] = 'B';
                        foreach (var l in list)
                        {
                            Q.Enqueue(l);
                        }
                    }
                    else
                    {
                        char ct = (char)(minecount + '0');//int转ascii码
                        board[x, y] = ct;
                    }
                }
            }
            return board;
        }
    }

按照BFS的思路来写，但是判断比较麻烦。