网站实现语言转换技术上该怎么做,百度建站多少钱,网页设计开发培训,免费营销型网站模版方格填数
如下的10个格子 ––– | | | | –––– | | | | | –––– | | | | –––
#xff08;如果显示有问题#xff0c;也可以参看【图1.jpg】#xff09;
填入0~9的数字。要求#xff1a;连续的两个数字不能相邻。 #xff08;左右、上下、对角都算相邻…方格填数
如下的10个格子 ––– | | | | –––– | | | | | –––– | | | | –––
如果显示有问题也可以参看【图1.jpg】
填入0~9的数字。要求连续的两个数字不能相邻。 左右、上下、对角都算相邻
一共有多少种可能的填数方案
请填写表示方案数目的整数。 注意你提交的应该是一个整数不要填写任何多余的内容或说明性文字。
一开始直接用dfs八个方向进行搜索结果很大也不知道问题在哪里 最后直接一个方格一个方格的填就出现了答案 先说一下思路吧 对于每一个0-9的数进行标记对于每一个坐标点进行填数 对填写的数进行判断如果可以直接填写然后进行下一个dfs 如果不可以进行寻找合适的数字找不到直接回溯到上一个dfs
答案1580 java代码实现 朋友做的代码效率比我高出N倍… package com.tjrac_java_2;public class QuanPaiLie {static int all0;static int[] num{-2,-2,-2,-2,-2,-2,-2,-2,10,10,10,-2,-2,10,10,10,10,-2,-2,10,10,10,-2,-2,-2,-2,-2,-2,-2,-2,};static int []useful{8,9,10,13,14,15,16,19,20,21};static int check(int i)//该位置方格的上左左上右上{ if(num[i]num[i-1]-1||num[i]num[i-1]1)return 0;else if(num[i]num[i-6]-1||num[i]num[i-6]1)return 0;else if(num[i]num[i-7]-1||num[i]num[i-7]1)return 0;else if(num[i]num[i-5]-1||num[i]num[i-5]1)return 0;elsereturn 1;}static int check_same(int i)//判断该方格中的数字是否被用过{for(int j0;ji;j)if(num[useful[j]]num[useful[i]])return 0;return 1;}static void func(int round){if(round9)//如果round9表示已经给所有方格添加数字{ all;return ;}elsefor(int i0;i9;i){num[useful[round]]i;//数字添加到方格中if(check_same(round)1check(useful[round])1)//判断该方格数字是否已经用过以及该填充的方格数字满足相邻不为1func(round1);//递归遍历下一个方格}}public static void main(String[] args) {func(0);System.out.println(all);}
}自己代码(58000ms呵呵。。。)
package com.tjrac_java_2;public class SumCount {//考虑到边界问题把数组行列扩大两位static int count0, sum 0;//count表示已经填充数的字格数。sum表示最后输出结果static int[][] go {{0,1},{1,0},{0,-1},{1,-1},{-1,0},{-1,1},{-1,-1},{1,1}};//右、下、左、左下、上、右上、左上、右下static int[][] newGo{{-1,0},{1,0},{0,-1},{0,1}};static int[] num new int[10];//用来判断该数字是否用过用过为1 否则为0static int[] road new int[11];static int flag0;static long start , end;public static void main(String[] args) {start System.currentTimeMillis();int [][] a new int [5][6];for (int i 0; i 10; i) {num[i]0;}for(int i0;i5;i){for(int j0;j6;j){a[i][j]11;//表示可以访问之所以为11因为方便判断不相邻}}for(int i0;i10;i){a[1][2]i;//控制第一个方格的值num[i]1;//标记i不能再用了count;flagi;//road[i]12;//路径DFS(a,1,2);a[1][2]11;num[i]0;count--;}System.out.println(总次数sum);System.out.println(用时(System.currentTimeMillis()-start));
// for (int is : road) {
// System.out.println(is);
// }}private static void DFS(int[][] a, int x, int y) {//递归出口//表示10个数字填充完毕System.out.println(ok);if(count 10 ){sum;return ;}else{//for(int i 0; i 8; i ){for(int i 0; i 4; i){//往相邻方格填数字int xx x go[i][0];int yy y go[i][1];//判断边界是否已经填充了数字满足相邻不为1if((xx1yy1) || (xx3yy4))continue;//因为11和44不能访问if(xx 1 xx 3 yy 1 yy 4 a[xx][yy] 11 ){//往该方格中放数字System.out.println(上个方格x:x-y:y);System.out.println(现在方格xx: xx yy yy);for( int k 0; k 10; k){//判断该数字是否被用过,并且数字不相邻if(num[k] 0 Math.abs(k-a[xx][yy1])!1 Math.abs(k-a[xx1][yy])!1 Math.abs(k-a[xx][yy-1])!1 Math.abs(k-a[xx1][yy-1])!1 Math.abs(k-a[xx-1][yy])!1 Math.abs(k-a[xx-1][yy1])!1 Math.abs(k-a[xx-1][yy-1])!1 Math.abs(k-a[xx1][yy1])!1){a[xx][yy] k;System.out.println(填入数字xx: xx yy 数字k右边a[xx][yy-1]);num[k]1;count;//road[count]xx*10yy;DFS(a,xx,yy);a[xx][yy] 11;num[k]0;count--;System.out.println(填入的方格总数count);/* if(count0){return;}*/}}}}//}}}
}
