1000字范文 > 最强大脑玲珑拼图游戏 java编程

最强大脑玲珑拼图游戏 java编程

时间：2019-06-22 08:33:24

相关推荐

最强大脑玲珑拼图游戏 java编程

代码

本文使用java编程来解决最强大脑中的玲珑拼图游戏，整体代码如下：

import java.util.*;public class LinLong {//大拼图边长private static int N;/** 记录拼图顺序* 保存的是拼图的序号* 第一个元素对应第一行第一列，其他以此类推* */private static List<Integer> SELECT = new ArrayList<>();/** 外围边的形状，从上面第一个开始数，顺时针方向，直到左面最上面* 1：圆圈；2：半圆；3：方形；4：三角形* 大小为4*N* */private static int[] EDGE;/** 记录所有小拼图形状* N*N行，4列* 以上右下左的顺序记录每个小拼图四周形状* */private static int[][] TU;/** 记录已使用的拼图* 大小为N*N* 索引i处记录第i块拼图的使用情况* 为0代表未使用，不为0代表已被使用* 不为0时又分4种情况，即直接使用，顺时针旋转90度，180度，270度* 4种情况分别用1,2,3,4来表示* */private static int[] USE;/** 记录所有可行结果* */private static int COUNT = 0;/** 主函数* */public static void main(String[] args) {/** 输入* 第一行一个正整数N，代表大拼图边长* 第二行N*4个数(取值范围是1,2,3,4)，代表外围边的形状* 接下来N*N行，每行4个数，代表所有小拼图的形状* */Scanner sc = new Scanner(System.in);N = sc.nextInt();EDGE = new int[N*4];TU = new int[N*N][4];USE = new int[N*N];for(int i=0;i<N*4;++i){EDGE[i] = sc.nextInt();}for(int i=0;i<N*N;++i){for(int j=0;j<4;++j){TU[i][j] = sc.nextInt();}}method(1);}/** 回溯方法* 参数i,代表本次调用是确定哪个位置的拼图* i=1时，代表此时已经放了0块拼图，接下来要确定第一块拼图（第一行第一列）该放哪一个* */public static void method(int i){//如果i大于N*N代表已经成功放了N*N块拼图，已经成功拼完，打印结果if(i > N*N){printResult();COUNT++;}/** pattern大小为4* 放入该处的拼图应该是什么形状* 以上右下左的顺序给出形状* 举例：若pattern = {1,0,0,3}* 代表放在该处的拼图，上面必须是圆圈，左面必须是方形，右面和下面可以是任意形状* */int[] pattern = getPattern(i);/** 找出所有满足要求的小拼图的序号* */List<Integer> all = select(pattern);/** all大小为0代表未找到* 这表明前面的拼图拼错了（虽然前面的所有小拼图可以互相吻合，但是从全局来看，是拼错的）* */if(all.size() == 0){return;}/** 遍历每一个小拼图* */for(Integer sel : all){/** 小拼图可以放在该位置，但还要知道它的旋转情况* 可能不旋转和顺时针180度这两种情况都可以放置，这种情况下返回一个列表{1,3}** */List<Integer> list = judge(pattern,TU[sel]);if(list.size() == 0){continue;}/** 遍历每一种可能的旋转情况* */for(Integer rot : list){//加入被选列表SELECT.add(sel);//更新USE,记录小拼图的使用情况USE[sel] = rot;//进行下一个拼图的选择method(i+1);/** 回溯* 从被选列表中移除本次选择的小拼图* USE对应的位置改为0* */SELECT.remove(SELECT.size()-1);USE[sel] = 0;}}}//确定patternpublic static int[] getPattern(int i){int[] res = new int[4];int row = (i-1)/N;int col = (i-1)%N;/** 确定‘上边’形状* 若是第一行，则是‘外层上边’对应处的形状* 若不是第一行，则是上一层拼图的‘下边’* */if(row == 0){res[0] = EDGE[col];}else {int tu_idx = SELECT.get((row-1)*N + col);int[] tu = TU[tu_idx];tu = rot(tu,USE[tu_idx]);res[0] = tu[2];}/** 确定'右边'* 若是最后一列，则是‘外层右边’对应的形状* 若不是最后一列，则是任意形状* */if(col == N-1){res[1] = EDGE[row+N];}/** 确定'下边'* 若是最后一行* 若不是最后一行，则是任意形状* */if(row == N-1){res[2] = EDGE[3*N-1-col];}/** 确定左边** */if(col == 0){res[3] = EDGE[4*N-1-row];}else {int tu_index = SELECT.get(row*N+col-1);int[] tu = TU[tu_index];tu = rot(tu,USE[tu_index]);res[3] = tu[1];}return res;}/** 找到所有满足pattern的小拼图的序号* */public static List<Integer> select(int[] pattern){List<Integer> res = new ArrayList<>();for(int i=0;i<N*N;++i){if(USE[i] != 0){continue;}if(judge(pattern,TU[i]).size() > 0){res.add(i);}}return res;}//对每一块小拼图，需要考虑所有4种情况：不旋转，旋转90,180,270public static List<Integer> judge(int[] pattern,int[] tu){List<Integer> list = new ArrayList<>();for(int i=1;i<=4;++i){if(judge(pattern,tu,i)){list.add(i);}}return list;}public static boolean judge(int[] pattern,int[] tu,int rot){tu = rot(tu,rot);for(int i=0;i<4;++i){int temp = pattern[i];if(temp == 0){continue;}if(temp != tu[i]){return false;}}return true;}/** 若一个小拼图的形状是 tu = {1,2,3,4}* 要旋转的次数是rot-1 = 1* 那么旋转后的小拼图形状是res = {3,4,1,2}* */public static int[] rot(int[] tu,int rot){int len = tu.length;int[] res = Arrays.copyOf(tu,len);for(int i=0;i<rot-1;++i){int temp = res[len-1];for(int j=len-1;j>0;--j){res[j] = res[j-1];}res[0] = temp;}return res;}/** 打印结果* N*N形式打印每个小拼图的所在位置* 举例：0:2出现在第一行第二列* 代表第一块拼图要放在第一行第二列，并且要顺时针旋转2次（注意，前面计算过程中顺时针旋转2次（180度）是用3代表，这是因为0被用来* 代表未使用，就只能用1来代表已使用并且未旋转，后面依次类推* */public static void printResult(){for(int i=0;i<N;++i){for(int j=0;j<N;++j){int idx = SELECT.get(i*N + j);int rot = USE[idx]-1;System.out.print(idx + ":" + rot + " ");}System.out.print("\n");}System.out.println("==================================");}}