LeetCode130. 被围绕的区域

 bfs题,主函数中枚举每一个起点,如果是'O'就开始bfs搜索,首先将'O'变为'X',然后将周围是'O'都入队。这里有个地方要注意,如果'O'并不是被四个'X'包围,也就是说'O'贴边,这种情况我们就不应该将他变为'X',所以程序中我用一个boolean变量isHuan来记录是否应该在枚举完之后将其变回去,而为了不让每一个点都“挖了”再“填回去”,每次访问到的点,我都用一个二维数组标记为访问过,只有没访问过的点才访问

class Solution {
    public int n,m;
    public int[] qx = new int[100000];
    public int[] qy = new int[100000];
    public int[][] dr = {{1,0},{-1,0},{0,1},{0,-1}};
    public boolean[][] v = new boolean[1000][1000];
    public boolean isHuan;
    public int check(int x,int y,int tail,char[][] board) {
        if(x >= 0 && x < n && y >= 0 && y < m) {
            if(board[x][y] == 'O') {
                qx[tail] = x;
                qy[tail] = y;
                board[x][y] = 'X';
                v[x][y] = true; 
                ++tail;
            } 
        } else {
            isHuan = true;
        }
        return tail;
    }       
    public void bfs(int x,int y,char[][] board) {
        isHuan = false;
        int head = 0;
        int tail = 1;//[hear,tail)
        qx[0] = x;
        qy[0] = y;
        board[x][y] = 'X';
        v[x][y] = true;
        while(head < tail) {
            int i;
            for(i = 0;i < 4;i++) {
                int nx = qx[head] + dr[i][0];
                int ny = qy[head] + dr[i][1];
                tail = check(nx,ny,tail,board);
            }
            if(i == 4)
                ++head;
        }
        if(isHuan)
            for(int i = 0;i < tail;i++) 
                board[qx[i]][qy[i]]= 'O';           
    }
    public void solve(char[][] board) {
        if(board.length == 0 || board[0].length == 0) 
            return;
        n = board.length;
        m = board[0].length;
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
                v[i][j] = false;
        for(int i = 0;i < n;i++) 
            for(int j = 0;j < m;j++) 
                if(board[i][j] == 'O' && !v[i][j])
                    bfs(i,j,board);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

22:因子分解

22:因子分解 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 输入一个数,输出其素因子分解表达式。 输入输入一个整数...

34012
来自专栏有趣的Python和你

微信好友全头像直接上图代码代码分析

1433
来自专栏深度学习自然语言处理

【python】命令行参数argparse用法详解

prog.py是我在linux下测试argparse的文件,放在/tmp目录下,其内容如下:

1013
来自专栏生信小驿站

R 热图绘制heatmap②

1034
来自专栏编程

说说正则表达式的使用

今日分享:正则表达式 一:正则表达式的定义及用途 正则表达式是一种特殊的字符串,字符串中的每个字符都含有特定的意义。使用者通过将正则中不同的字符组合成不同的字符...

1968
来自专栏云时之间

深度学习与神经网络:制作数据集,完成应用(1)

在这一篇文章里,我们将继续上一篇文章的工作,并且在上一篇文章的前提下加入数据集的制作,最终我们将完成这个全连接神经网络的小栗子.

8056
来自专栏Golang语言社区

Golang语言--计算运行的时间

函数time.Since() 计算golang运行的时间是非常有用的性能衡量指标,特别是在并发基准测试中。下面将介绍如何简单地使用Go语言来计算程序运行的时间。...

3588
来自专栏CSDN技术头条

使用Go语言来理解Tensorflow

【译者注】本文通过一个简单的Go绑定实例,让读者一步一步地学习到Tensorflow有关ID、作用域、类型等方面的知识。以下是译文。 Tensorflow并不是...

26710
来自专栏CreateAMind

深度学习框架TensorFlow 官方文档中文版

813
来自专栏C/C++基础

Linux命令(12)——wc命令

(3)从文件读取输入文件名。如果有多个文件名,并且希望 wc 从一个文件中读取它们,那么使用-files0-from 选项。这里将文件名称必须以NULL字符结束...

1011

扫码关注云+社区

领取腾讯云代金券