2018蓝桥杯第五次模拟赛--连连看

本文主要是介绍2018蓝桥杯第五次模拟赛--连连看，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

连连看是一款非常有意思的游戏。

我们可以把任意两个在图的在边界上的相同的方格一起消掉，比如把两个 $4$ 消掉以后，

每次消掉两个方格的时候，都有会获得一个分数，第 $i$ 次消的分数为 $i\times$ 方格的值。比如上面的消法，是第一次消，获得的分数为 $1\times 4=4$。

请你帮忙最优操作情况下，获得的分数最多为多少。

解题思路：用 dfs 求解，每一次搜索，找到两个相同的边界点，标记即可。

检测边界点的方法也很简单，只需要一个点的四个方向中有一个点在地图外或者已经被标记，那么这个点就是边界点。

package 连连看;public class Main {static int a[][]={{1,4,2,5},{2,1,2,1},{3,1,3,2},{2,5,3,4}};static int n=4;static int ants=0;static boolean used[][]=new boolean[n][n];	public static void main(String[] args) {// TODO Auto-generated method stubdfs(1,0);System.out.println(ants);}public static boolean ok(int x,int y){if(x>=0&&x<n&&y>=0&&y<n) return true;return false;}public static boolean check(int x,int y){if(used[x][y]) return false;int dir[][]={{0,1},{0,-1},{-1,0},{1,0}};int nx=0,ny=0;for(int i=0;i<4;i++){nx=x+dir[i][0];ny=y+dir[i][1];if(!ok(nx,ny)) return true;if(used[nx][ny]) return true;}return false;}public static void dfs(int step,int s){ants=Math.max(s,ants);for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(check(i,j)){for(int p=0;p<n;p++){for(int q=0;q<n;q++){if(p==i&&q==j)	continue;if(a[i][j]==a[p][q]&&check(p,q)){used[i][j]=true;used[p][q]=true;dfs(step+1,s+step*(a[p][q]));used[i][j]=false;used[p][q]=false;}}}}}}}}

这篇关于2018蓝桥杯第五次模拟赛--连连看的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---