一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 223|回复: 2
收起左侧

[Leetcode] Surrounded Region 坐标编码想不明白

[复制链接] |试试Instant~ |关注本帖
熊亮亮111 发表于 2015-11-3 22:58:13 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
LeetCode Surrounded Region 这道题X X X XX O O XX X O XX O X X

代码如下:
public void solve(char[][] board) {
    if(board==null || board.length<=1 || board[0].length<=1)
        return;

    //第一行和最后一行进行fill
    for(int i=0;i<board[0].length;i++){
        fill(board,0,i);
        fill(board,board.length-1,i);
    }

    //第一列和最后一列进行fill
    for(int i=0;i<board.length;i++){
        fill(board,i,0);
        fill(board,i,board[0].length-1);
    }

    //对于当前格子中,所有O变成X(说明符合要求,没有被变成#),所有#变成O
    for(int i=0;i<board.length;i++){
        for(int j=0;j<board[0].length;j++){
            if(board[j]=='O')
                board[j]='X';
            else if(board[j]=='#')
                board[j]='O';               
        }
    }
}

private void fill(char[][] board, int i, int j){
    if(board[j]!='O')
        return;
    board[j] = '#';
    //利用BFS
    LinkedList<Integer> queue = new LinkedList<Integer>();
    //先将矩阵的横纵坐标编码
    int code = i*board[0].length+j;
    queue.add(code);
    while(!queue.isEmpty()){
        code = queue.poll();
       int row = code/board[0].length;//从code中还原横坐标
        int col = code%board[0].length;//从code中还原纵坐标

        if(row>=1 && board[row-1][col]=='O'){//当前元素上边是否为0
            queue.add((row-1)*board[0].length + col);
            board[row-1][col]='#';
        }

        if(row<=board.length-2 && board[row+1][col]=='O'){//当前元素下面是否为0
            queue.add((row+1)*board[0].length + col);
            board[row+1][col]='#';
        }

        if(col>=1 && board[row][col-1]=='O'){//当前元素左边是否为0
            queue.add(row*board[0].length + col-1);
            board[row][col-1]='#';
        }

        if(col<=board[0].length-2 && board[row][col+1]=='O'){//当前元素右边是否为0
            queue.add(row*board[0].length + col+1);
            board[row][col+1]='#';
        }            
    }
}

代码中红色部分就是我不太明白的地方,为什么不能直接用横纵坐标? 编码的时候,为什么是int code = i*board[0].length+j; 而不能用 int code=i*board.length+j;
谢谢大神指教!
stellari 发表于 2015-11-4 08:23:30 | 显示全部楼层
可以用横纵坐标,但那样的话,每次向queue中压入的就会是2个值。这样就可能需要用pair或者自定义的类来包装一下,代码就会略微麻烦。当然也可以选择不包装直接将2个int值依次压入queue,但是个人感觉安全性不好。

不能写成board.length。因为 i 表示第 i 行,i * board[0].length是前 i 行的总元素数目。


回复 支持 反对

使用道具 举报

 楼主| 熊亮亮111 发表于 2015-11-4 08:30:46 | 显示全部楼层
stellari 发表于 2015-11-4 08:23
可以用横纵坐标,但那样的话,每次向queue中压入的就会是2个值。这样就可能需要用pair或者自定义的类来包装 ...

想明白了 谢谢啦
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 21:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表