C#, BSF solution and pass at the first time


  • 0
    D
    public class Solution {
        public void Solve(char[,] board) {
            int row = board.GetLength(0);
            int col = board.GetLength(1);
        
            Queue<Tuple<int,int>> q = new Queue<Tuple<int,int>>();
            
            for(int i=0; i<row;i++){
                if(board[i,0] == 'O'){
                    board[i,0] = '+';
                    q.Enqueue(new Tuple<int,int>(i,0));
                }
                
                if(board[i,col-1] == 'O'){
                    board[i, col-1] = '+';
                    q.Enqueue(new Tuple<int,int>(i,col-1));
                }
            }
            
            for(int i = 0; i< col; i++){
                if(board[0,i] == 'O'){
                    board[0,i] = '+';
                    q.Enqueue(new Tuple<int,int>(0,i));
                }
                if(board[row -1, i] == 'O'){
                    board[row-1,i] = '+';
                    q.Enqueue(new Tuple<int,int>(row -1, i));
                    
                }
            }
            
            while(q.Count != 0){
                var output = q.Dequeue();
                int x = output.Item1;
                int y = output.Item2;
                
                if(x - 1 >=0 && board[x-1,y] == 'O'){board[x-1,y] = '+'; q.Enqueue(new Tuple<int,int>(x-1,y)); }
                if(x + 1 < row && board[x+1,y] == 'O'){board[x+1,y] = '+'; q.Enqueue(new Tuple<int,int>(x+1,y)); }
                if(y - 1 >=0 && board[x,y -1] == 'O'){board[x,y -1] = '+'; q.Enqueue(new Tuple<int,int>(x,y -1)); }
                if(y + 1 < col && board[x,y +1] == 'O'){board[x,y +1] = '+'; q.Enqueue(new Tuple<int,int>(x,y +1)); }
            }
            
            // replace all remain O to X and replace all + to O
            for(int i=0; i< row; i++){
                for(int j = 0; j< col; j++){
                    if(board[i,j] == 'O') board[i,j] = 'X';
                }
            }
    
            for(int i=0; i< row; i++){
                for(int j = 0; j< col; j++){
                    if(board[i,j] == '+') board[i,j] = 'O';
                }
            }
                    
        }
    }

  • 0
    L

    I've got almost the same idea as yours ,but failed.I dont do BFS one time for all the node.Instead ,I do the BFS one time a node.

    public class Solution {
    int xl;
    int yl;
    char[][] ob;
    
    public void solve(char[][] board) {
    	this.ob = board;
    	xl = board.length;
    	if (xl == 0)
    		return;
    	yl = board[0].length;
    
    	for (int y = 0; y < yl; y++) {
    		if (board[0][y] == 'O')
    			bfs(0, y);
    		if (board[xl - 1][y] == 'O')
    			bfs(xl - 1, y);
    	}
    
    	for (int x = 0; x < xl; x++) {
    		if (board[x][0] == 'O')
    			bfs(x, 0);
    		if (board[x][yl - 1] == 'O')
    			bfs(x, yl - 1);
    	}
    
    	for (int i = 0; i < xl; i++) {
    		for (int j = 0; j < yl; j++) {
    			if (board[i][j] == 'O')
    				board[i][j] = 'X';
    			if (board[i][j] == '+')
    				board[i][j] = 'O';
    		}
    	}
    }
    
    private class Pair {
    	int x;
    	int y;
    
    	Pair(int x, int y) {
    		this.x = x;
    		this.y = y;
    	}
    }
    
    public void bfs(int ii, int jj) {
    
    	Queue<Pair> q = new LinkedList<Pair>();
    	q.offer(new Pair(ii, jj));
    	while (!q.isEmpty()) {
    		Pair t = q.poll();
    		ob[t.x][t.y] = '+';
    		int i = t.x;
    		int j = t.y;
    		if (i > 0 && ob[i - 1][j] == 'O' && ob[i - 1][j] != '+') {
    			q.offer(new Pair(i - 1, j));
    		}
    		if (i < xl - 1 && ob[i + 1][j] == 'O' && ob[i + 1][j] != '+') {
    			q.offer(new Pair(i + 1, j));
    		}
    		if (j > 0 && ob[i][j - 1] == 'O' && ob[i][j - 1] != '+') {
    			q.offer(new Pair(i, j - 1));
    		}
    		if (j < yl - 1 && ob[i][j + 1] == 'O' && ob[i][j + 1] != '+') {
    			q.offer(new Pair(i, j + 1));
    		}
    	}
    
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.