首页 > 其他分享 >130. 被围绕的区域(leetcode)

130. 被围绕的区域(leetcode)

时间:2024-10-07 17:44:02浏览次数:6  
标签:int 围绕 char vis 130 board new leetcode

https://leetcode.cn/problems/surrounded-regions/

class Solution {
    int n;
    int m;
    boolean[][] vis;
    char[][] board;
    int[] dx=new int[]{0,1,0,-1};
    int[] dy=new int[]{1,0,-1,0};
    public void solve(char[][] board) {
        // 从边缘O出发,通过flood fill,标记和边缘相连的联通块,再把剩余区域标记为X
        n=board.length;
        m=board[0].length;
        vis=new boolean[n][m];
        this.board=board;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                // 边缘的点满足性质: x==0||n-1 或者 y==0||m-1
                if(i!=0 && i!=n-1 &&  j!=0 && j!=m-1)continue;
                if(board[i][j]=='O' && vis[i][j]==false)
                {
                    dfs(i,j);
                }
            }
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(vis[i][j]==false && board[i][j]=='O')board[i][j]='X';
            }
    }  

    void dfs(int x,int y)
    {
        vis[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0 && b>=0 && a<n && b<m && vis[a][b]==false && board[a][b]=='O')
            {
                dfs(a,b);
            }
        }
    }

}

 

标签:int,围绕,char,vis,130,board,new,leetcode
From: https://www.cnblogs.com/lxl-233/p/18450371

相关文章

  • 463. 岛屿的周长(leetcode)
    https://leetcode.cn/problems/island-perimeter/description/思路:遍历岛屿,一旦遍历到边界或者水则周长++classSolution{intres;boolean[][]vis;int[][]grid;int[]dx=newint[]{0,1,0,-1};int[]dy=newint[]{1,0,-1,0};intn;intm......
  • Day 28 动态规划part01| LeetCode 509.斐波那契数,70.爬楼梯,746.使用最小花费爬楼梯
    理论基础包含题目类别:基础类(斐波那契、爬楼梯)、背包问题、打家劫舍、股票问题、子序列问题解题关键DP数组定义以及下标的含义递推公式DP数组如何初始化遍历顺序打印DP数组509.斐波那契数509.斐波那契数classSolution{publicintfib(intn){......
  • Day 24 贪心算法part02| LeetCode 122.买卖股票的最佳时机II,55.跳跃游戏,45.跳跃游戏II
    122.买卖股票的最佳时机II局部最优:每天的正利润全局最优:每天的正利润之和121.买卖股票的最佳时机classSolution{publicintmaxProfit(int[]prices){intres=0;for(inti=1;i<prices.length;i++){i......
  • Leetcode 10. 正则表达式匹配
    1.题目基本信息1.1.题目描述给你一个字符串s和一个字符规律p,请你来实现一个支持‘.’和‘*’的正则表达式匹配。‘.’匹配任意单个字符‘*’匹配零个或多个前面的那一个元素所谓匹配,是要涵盖整个字符串s的,而不是部分字符串。1.2.题目地址https://leetcode.c......
  • # 2024-2025-1 20241301 《计算机基础与程序设计》第二周学习总结
    这个作业属于哪个课程<2024-2025-1-计算机基础与程序设计>这个作业要求在哪里<2024-2025-1计算机基础与程序设计第一周作业>这个作业的目标<概括性地了解计算机系统,解决为什么要学习编程的问题>作业正文https://www.cnblogs.com/HonJo/p/18449597教材学习内......
  • 684. 冗余连接(leetcode)
    https://leetcode.cn/problems/redundant-connection/classSolution{publicint[]findRedundantConnection(int[][]edges){//思路:遍历边,不断的加入相连的点到集合中,直到遍历到同在一集合的两个顶点位置,这个边就可以是答案init(edges.length);......
  • 2024-2025 20241308《计算机基础与程序设计》第二周学习总结
    这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK02这个作业的目标阅读《计算机科学概论》和《C语言程序设计》的第一章内容并从中学习感悟,找到不懂的问题并想办法解决作......
  • 547. 省份数量(leetcode)
    https://leetcode.cn/problems/number-of-provinces/并查集模版题classSolution{int[]p;voidinit(intn){p=newint[n];for(inti=0;i<n;i++)p[i]=i;}intfind(intx){returnx==p[x]?x:(p[x]=find(p[x]));......
  • LeetCode hot100-二叉树篇思路总结
    跌跌撞撞看代码随想录看leetcode官方题解,终于写完了hot100的二叉树部分。这是我第一次学习如何正式的用java去写一个二叉树首先在自己的编译器里定义一个TreeNode类,以便于后面刷题的时候复用publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;......
  • # 2024-2025-1 学号(2024130) 《计算机基础与程序设计》第二周学习总结
    作业信息|这个作业属于哪个课程|<[2024-2025-1-计算机基础与程序设计]>(https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP))||-- |-- ||这个作业要求在哪里|<[2024-2025-1计算机基础与程序设计第一周作业]>(https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP/home......