Untitled
package practice; import java.io.FileInputStream; import java.time.chrono.MinguoChronology; import java.util.Scanner; public class conxe { static int N,max,sum; static char[][] map; static int[] dichchuyenrow = {-1,0}; static int[] dichchuyencol = {0,-1}; static void try1(int index) { if(index == N *N) { if(max < sum) { max = sum; } return; } int r = index/N; int c = index%N; //DAT CON XE if(map[r][c] == 'X') { try1(index+1); } else { int check= 0; for(int i = r;i>=0 ;i--) { int nextr = i -1; int nextc = c; if(nextr >=0 && nextr <N && nextc>=0 && nextc <N) { if(map[nextr][nextc] == 'X') { break; } if(map[nextr][nextc] == 'D') { check = 1; break; } } } for(int i = c;i>=0 ;i--) { int nextr = r; int nextc = i-1; if(nextr >=0 && nextr <N && nextc>=0 && nextc <N) { if(map[nextr][nextc] == 'X') { break; } if(map[nextr][nextc] == 'D') { check = 1; break; } } } if(check == 0) { sum+=1; map[r][c] = 'D'; try1(index+1); sum-=1; map[r][c] = '.'; } // ko dat xe try1(index+1); } } public static void main(String[] args) throws Exception { System.setIn(new FileInputStream("src/practice/input.txt")); Scanner scanner = new Scanner(System.in); int T = scanner.nextInt(); for(int t=1;t<=T;t++) { System.out.println("Case #"+t); N = scanner.nextInt(); map = new char[N][N]; for(int i =0;i<N;i++) { String string = scanner.next(); for(int j =0;j<N;j++) { map[i][j] = string.charAt(j); } } max =0; try1(0); System.out.println(max); } } }
Leave a Comment