程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode]Surrounded Regions

[LeetCode]Surrounded Regions

編輯:C++入門知識

[LeetCode]Surrounded Regions


Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

這道題利用深搜會StackOverFlow,思想是所有在最邊的'O'及其相連的區域都不會覆蓋,找出所有這樣的區域,記錄在isChecked數組中,遍歷修改,其中有一句很重的判重,搞了2個小時才找到。

public class Solution {
	boolean isChecked[][];
	int seq = 0;
    public void solve(char[][] board) {
    	if(board.length==0) return;
    	if(board.length<=2||board[0].length<=2) return;
    	int row = board.length, column = board[0].length;
    	isChecked = new boolean[row][column];
    	//下面的連個循環用來搜索靠邊,且為'O'的部分,然後利用寬搜搜索所有區域
    	for(int i=0;i current = new LinkedList<>();
    	current.offer(new int[]{xd,yd});
    	//不記錄廣搜分層
    	while(!current.isEmpty()){
			int[] cd = current.poll();
			int x=cd[0], y = cd[1];
			isChecked[x][y] = true;
			seq++;
			int move[][] ={{x-1,y},{x,y+1},{x+1,y},{x,y-1}};
			for(int i=0;i<4;i++){
				int dx = move[i][0], dy = move[i][1];
				if(dx<0||dx>=row||dy<0||dy>=column||isChecked[dx][dy]||board[dx][dy]!='O') continue;
				//下面一句話巨重要,當找到'O'的時候就要記錄它已經被搜索過,如果沒有記錄則其他的路徑也會搜索到該點
				isChecked[dx][dy] = true;
				current.add(new int[]{dx,dy});
			}
    	}
    	System.out.println(seq);
    }
}




·


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved