代码转换：
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int N=310; static char[][] arr=new char[N][N]; static boolean[][] visit=new boolean[N][N]; static int[] dx= {1,-1,0,0}; static int[] dy= {0,0,-1,1}; static int tmp=2; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int k=sc.nextInt(); for(int i=0;i<n;++i) { arr[i]=sc.next().toCharArray(); } Queue<int[]> queue=new LinkedList<>(); queue.offer(new int[]{2,2}); visit[2][2]=true; int count=0; while(!queue.isEmpty()) { int size=queue.size(); while(size-->0) { int[] curr=queue.poll(); int x=curr[0]; int y=curr[1]; if(x==n-3&&y==n-3) { System.out.println(count); return; } for(int i=0;i<4;++i) { int a=x+dx[i]; int b=y+dy[i]; if(a-tmp>=0&&a+tmp<n&&b-tmp>=0&&b+tmp<n&&!visit[a][b]&&check(a,b)) { queue.offer(new int[]{a,b}); visit[a][b]=true; } } //需要再把自己当前位置加入队列，表示原地等待 queue.offer(new int[]{x,y}); } count++; if(count==k) tmp=1; if(count==2*k) tmp=0; } } //判断当前位置小明是否能够移动到此 static boolean check(int a,int b){ for (int i =a-tmp; i<=a+tmp; i++) { for (int j =b-tmp; j<=b+tmp ; j++) { if (arr[i][j]=='*') return false; } } return true; } }
🎏4.合根植物（并查集）
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
题目链接：合根植物http://lx.lanqiao.cn/problem.page?gpid=T2850
这道题考察的就是基础的并查集题目。并查集是一种很实用并且比较简单容易理解的数据结构。大家不要觉得很难，而且并查集的题目套模板即可，记住那几个方法的实现就可以，而且这道题目属于往年的国赛真题，并查集在省赛出现的概率也是非常大的。
如果大家不知道该如何入手并查集，可以去看一下黑马的数据结构教学视频： 黑马数据结构
代码转换：
import java.util.Scanner; public class Main { static int N=1010; static int[][] arr=new int[N][N]; //并查集 static int[] p=new int[N*N]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { arr[i][j]=i*m+j; } } int count=m*n; for(int i=1;i<=n*m;++i) p[i]=i; int k=sc.nextInt(); while(k-->0) { int a=sc.nextInt(); int b=sc.nextInt(); int root1=find(a); int root2=find(b); if(root1!=root2){ p[root1]=root2; count--; } } System.out.println(count); } static int find(int x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } }
🎓5.分考场（回溯）
n个人参加某项特殊考试。
为了公平，要求任何两个认识的人不能分在同一个考场。
求最少需要分几个考场才能满足条件。
题目链接：分考场http://lx.lanqiao.cn/problem.page?gpid=T2849
首先这道题目的数据范围很小，n最大只能取到100，所以如此我们可以考虑使用回溯去进行爆搜。因为确实这道题看上去没有很好的解决办法，但是这道题目使用回溯也非常有讲究，因为它需要双回溯，也就是回溯两次。
为什么会出现这种情况呢？因为爆搜要考虑所有的情况。这个我们先不提
这道题我我先是用的贪心的想法：当选择一名学生时，考虑第一个考场，是否能把他放进去，不能就看第二个，如果全都不行就重新开一个考场给他，直到所有学生放进去。但一名学生他可能是可以出现在多个考场的，不同的考场都会影响我们的答案，所以这样只拿了40分。
之所以要讲贪心的错误做法，正是因为回溯弥补了贪心的缺陷，当我们对一个学生对已有考场进行判断时，先考虑A考场，可以放入我们就先放入，往后判断完以后再回溯不放入，接着再考虑B考场，也是类似A一样的考虑。最后再考虑如果这个学生无法安排进去则需要新开一个考场，无论有没有考场放入他，因为我们要考虑所有的情况。这样考虑每次安排完所有学生后看使用了多少个考场，然后取一个最小值。
代码转换：
import java.util.*; public class Main { static int n,m,N=110; static List<Integer>[] list=new ArrayList[N]; static int ans=100; static boolean[][] map=new boolean[N][N]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); for (int i = 0; i < m; i++) { int a=sc.nextInt(); int b=sc.nextInt(); map[a][b]=map[b][a]=true; } for (int i = 1; i<=n ; i++) { list[i]=new ArrayList<>(); } dfs(1,0); System.out.println(ans); } //st是学生，cl是教室数量 static void dfs(int st,int cl){ //这步是剪枝操作，很重要，否则可能导致超时 //当我们判断已用教室已经大于等于找到的最小情况 //那我们没有必须继续搜索，因为它一定不是答案 if (cl>=ans) return; //到这一步说明找到了一种更小的方案 if (st>n){ ans=cl; return; } for (int i = 1;i<=cl ; i++) { int j=0; for (;j<list[i].size();++j){ if(map[st][list[i].get(j)]) break; } //说明和这个教室全部学生都不相等 if (j==list[i].size()){ //放入学生 list[i].add(st); dfs(st+1,cl); //回溯 list[i].remove(list[i].size()-1); } } //走到这步还没找到教室说明需要新教室 list[cl+1].add(st); dfs(st+1,cl+1); //回溯 list[cl+1].remove(list[cl+1].size()-1); } }
