AUG!!! JAVA


  • 0
    public class Solution {
            int[][] validGrid ;
    	List<List<String>> res;
    	int[] pos;
    	int N;
            public List<List<String>> solveNQueens(int n) {
            res = new ArrayList<>();
    		N = n;
    		if(n == 0) return res;
    		pos = new int[N];
    		validGrid = new int[n][n];
    		backtrack(1,n);
    		return res;
        }
    	public void backtrack(int level, int n)
    	{
    		
    		if(level > n)
    			return;
    		for(int start = 0; start < n; start++)
    		{
    			if(validGrid[level - 1][start] == 0)
    			{
    				ChangeGrid(level - 1, start,true);
    				pos[level - 1] = start;
    				if(level == n)
    					addResult();
    				
    				backtrack(level + 1, n);
    				ChangeGrid(level - 1,start, false);
    				
    			}
    		}
    	}
    	public void addResult()
    	{
    		List<String> curr = new ArrayList<>();
    		char[] arr = new char[N];
    		Arrays.fill(arr,'.');
    		for(int i = 0; i < N; i++)
    		{
    			arr[pos[i]] = 'Q';
    			curr.add(new String(arr));
    			arr[pos[i]] = '.';
    		}
    		res.add(curr);
    	}
    	public void ChangeGrid (int row, int col, boolean add)
    	{
    		int num = row +1;
    		int check = 0;
    		int len = validGrid.length;
    		if(!add)
    		{
    			check = num;
    			num = 0;
    		}
    		for(int i = 0 ; i < len; i++)
    		{
    			if(validGrid[row][i] == check)
    				validGrid[row][i] = num;
    		}
    		for(int i = 0 ; i < len; i++)
    		{
    			if(validGrid[i][col] == check)
    				validGrid[i][col] = num;
    		}
    		for(int i = 0; i < len; i++)
    		{
    			int col1 = col - row + i;
    			if(col1 >=0 && col1 < len)
    			{
    				if(validGrid[i][col1] == check)
    					validGrid[i][col1] = num;
    			}
    			
    			int col2 = col - (len - 1 - row) + i;
    			if(col2 >=0 && col2 < len)
    			{
    				if(validGrid[len - 1 - i][col2] == check)
    					validGrid[len - 1 - i][col2] = num;
    			}
    		}
    	}
    }
    

Log in to reply
 

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