感觉他们的数据量应该特别的小......我最后一题直接暴力模拟竟然过了(N多重嵌

2019-09-27 22:58 深圳大学

关注

感觉他们的数据量应该特别的小......我最后一题直接暴力模拟竟然过了(N多重嵌套循环)... 2的 package WY; import java.util.HashMap; import java.util.Map; import java.util.Scanner; /** * 思路: * 1. 暴力生成6个字母的全部排列试一下? */ public class wangyi02 { public static void main(String[] args){ wangyi02 wangyi02 = new wangyi02(); wangyi02.Input(); } int T; String str; String[] array = { "A","S","D","F","G","H" }; String[] finalResult = new String[6]; // 用于表示某个字母目前在哪个位置 Map<String,Integer> finalMapping = new HashMap<>(); boolean[] visited = new boolean[6]; // 最小代价 int minReuslt = Integer.MAX_VALUE; public void Input(){ Scanner in = new Scanner(System.in); T = in.nextInt(); for(int i=0;i<T;i++){ str = in.next(); minReuslt = Integer.MAX_VALUE; DFS(0); System.out.println(minReuslt); } } public void DFS(int index){ if(index==6){ // finalResult是最终生成的排列 Compute(); return; } for(int i=0;i<array.length;i++){ if(!visited[i]){ visited[i] = true; finalResult[index] = array[i]; finalMapping.put(array[i],index); DFS(index+1); visited[i] = false; } } } public void Compute(){ // 记录当前手放在哪个位置上 int nowIndex = 0; // 代价 int result = 0; for(int i=0;i<str.length();i++){ String ch = str.charAt(i)+""; result += Math.abs(nowIndex - finalMapping.get(ch)); nowIndex = finalMapping.get(ch); } if(result<minReuslt){ minReuslt = result; } } } 3的 package WY; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; /** * 思路: * 1. 对着题意模拟. * 坑: * 1. 数量最多指的不是在整个游戏里数量最多,是指联通数量最多. * 举例: * 131 * 331 * 这里3的联通数量最多,因为1的联通数量最大是2,3是3 */ public class wangyi03 { public static void main(String[] args){ wangyi03 wangyi03 = new wangyi03(); wangyi03.Input(); } int T; int M,N; char[][] array; // 当前要消除的方块的具***置 int nowRemoveI,nowRemoveJ; public void Input(){ Scanner in = new Scanner(System.in); T = in.nextInt(); for(int i=0;i<T;i++){ M = in.nextInt(); N = in.nextInt(); array = new char[M][N]; for(int j=0;j<M;j++){ array[j] = in.next().toCharArray(); } // 重置所有状态后进行计算 nowRemoveI = 0; nowRemoveJ = 0; DFScount = 0; Slove(); } } public void Slove(){ while (nowRemoveI!=-1 && nowRemoveJ!=-1) { // 第一步,找到要进行消除的方块 // 规则: // 1. 数量最多; 2. 编号最小; 3. 行最小,列最小; GetRemoveIndex(); if(nowRemoveI==-1 && nowRemoveJ==-1) break; // 第二步,消除目标方块,并且应用规则重排整个数组(所有已空位置设为'#') Remove(); // 每完成一步输出一下 // Print(); // System.out.println(); } int c = 0; // 第三步,找到剩余格子数量并输出 for(int i=0;i<M;i++) for(int j=0;j<N;j++) if(array[i][j]!='#') c++; System.out.println(c); } int DFScount = 0; int[][] dir = new int[][]{ {1,0}, // 下 {0,1}, // 右 {-1,0}, // 上 {0,-1} // 左 }; public void DFS(int x,int y,char target,boolean[][] visited){ // 不搜空的地方 if(target=='#') return; for(int i=0;i<4;i++){ int tempX = x+dir[i][0]; int tempY = y+dir[i][1]; if(tempX>=0&&tempX<M&&tempY>=0&&tempY<N && !visited[tempX][tempY] && array[tempX][tempY]==target){ visited[tempX][tempY] = true; DFScount ++; DFS(tempX,tempY,target,visited); } } } // DFS找到联通数量最多的方块 public void FindMaxCount(int[] count){ boolean[][] visited = new boolean[M][N]; for(int i=0;i<M;i++){ for(int j=0;j<N;j++){ if(!visited[i][j] && array[i][j]!='#'){ DFScount = 1; visited[i][j] = true; DFS(i,j,array[i][j],visited); if(DFScount>count[array[i][j]-'0']){ count[array[i][j]-'0'] = DFScount; } } } } } public void GetRemoveIndex(){ // 首先找数量最多的 int maxCount = 0; // count[i]表示第i个数字的最大联通数量 int[] count = new int[10]; FindMaxCount(count); for(int i=0;i<10;i++) maxCount = Math.max(maxCount,count[i]); if(maxCount == 1 || maxCount==0){ // 最大数量为1的时候,说明已经没有方块可以消除了 nowRemoveI = -1; nowRemoveJ = -1; return; } char minIndex = 0; // 找到数量最多之中的编号最小的 for(int i=0;i<10;i++){ if(count[i]==maxCount){ minIndex = (char)(i+'0'); break; } } boolean[][] visited = new boolean[M][N]; // 找到编号最小的之中行最小,列最小的(还得是数量最多的) for(int i=0;i<M;i++){ for(int j=0;j<N;j++){ if(array[i][j]==minIndex && !visited[i][j]) { visited[i][j] = true; DFScount = 1; DFS(i, j,minIndex,visited); if(DFScount == maxCount){ nowRemoveI = i; nowRemoveJ = j; return; } } } } } public void DFSRemove(int x,int y,char target,boolean[][] visited){ // 不搜空的地方 if(target=='#') return; array[x][y] = '#'; for(int i=0;i<4;i++){ int tempX = x+dir[i][0]; int tempY = y+dir[i][1]; if(tempX>=0&&tempX<M&&tempY>=0&&tempY<N && !visited[tempX][tempY] && array[tempX][tempY]==target){ visited[tempX][tempY] = true; DFSRemove(tempX,tempY,target,visited); } } } public void Remove(){ boolean[][] visited = new boolean[M][N]; DFSRemove(nowRemoveI,nowRemoveJ,array[nowRemoveI][nowRemoveJ],visited); // 重排数组,只要一列中#上方的不是#,那么就继续重排 for(int j=0;j<N;j++){ while (true) { boolean isBreak = true; for (int i = 0; i < M; i++) { // 如果下面的格子为空,那么将它与它下面的格子交换 int bottom = i+1; if(bottom<M && array[bottom][j]=='#'){ array[bottom][j] = array[i][j]; array[i][j] = '#'; } } for(int i=0;i<M;i++){ // 只要#上方不是#,就继续重排 int top = i-1; if(top>=0 && array[i][j]=='#' && array[top][j]!='#') { isBreak = false; break; } } if(isBreak) break; } } // for(int i=0;i<M;i++){ // for(int j=0;j<N;j++){ // // 如果下面的格子为空,那么将它与它下面的格子交换 // int bottom = i+1; // if(bottom<M && array[bottom][j]=='#'){ // array[bottom][j] = array[i][j]; // array[i][j] = '#'; // } // } // } // 第一列为空的情况下,不停的运行这段代码 while (true) { // 第一列空格子数量 int oneColEmpty = 0; // 是否整个数组都为空 boolean isEmpty = true; // 如果某一列为空,那么将其右边的一列来取代他 for (int j = 0; j < N; j++) { // 该列空格子数 int colEmpty = 0; for (int i = M - 1; i >= 0; i--) { if (array[i][j] == '#') colEmpty++; if(array[i][j]=='#' && j==0) oneColEmpty++; } int right = j + 1; // 空格子数==M表示该列为空,那么让其右边的一列取代他 if (colEmpty == M && right < N) { for (int i = 0; i < M; i++) { array[i][j] = array[i][right]; array[i][right] = '#'; } } if(colEmpty!=M) isEmpty = false; } if(oneColEmpty!=M) break; // 整个数组为空的情况下也结束循环 if(isEmpty) break; } } public void Print(){ for(int i=0;i<M;i++){ for(int j=0;j<N;j++){ System.out.print(array[i][j]); } System.out.println(); } } } 代码写的比较烂....因为时间比较赶...献丑了5555

牛客热帖