美高梅网投网站-美高梅手机网投-美高梅官方网站
做最好的网站

您的位置:美高梅网投网址 > 美高梅手机网投 > 对于整点,反复移动到一个尚未经过的"相邻"的点

对于整点,反复移动到一个尚未经过的"相邻"的点

发布时间:2019-09-22 16:55编辑:美高梅手机网投浏览(109)

    原创

    题目:滑动解锁


    滑动解锁是智能手机一项常用的功能。你需要在3x3的点阵上,从任意一个点开始,反复移动到一个尚未经过的"相邻"的点。这些划过的点所组成的有向折线,如果与预设的折线在图案、方向上都一致,那么手机将解锁。

    如图p1.png所示的螺旋折线经过平面上所有整点恰好一次。
    对于整点,我们定义它到原点的距离dis是从原点到的螺旋折线段的长度。
    例如dis=3, dis=9
    给出整点坐标,你能计算出dis吗?

    所谓两个点“相邻”:当且仅当以这两个点为端点的线段上不存在尚未经过的点。

    X和Y
    对于40%的数据,-1000 <= X, Y <= 1000
    对于70%的数据,-100000 <= X, Y <= 100000
    对于100%的数据, -1000000000 <= X, Y <= 1000000000

    此外,许多手机都约定:这条折线还需要至少经过4个点。

    输出dis

    为了描述方便,我们给这9个点从上到下、从左到右依次编号1-9。即如下排列:

    0 1

    1 2 3 4 5 6 7 8 9

    3

    那么1->2->3是非法的,因为长度不足。 1->3->2->4也是非法的,因为1->3穿过了尚未经过的点2。 2->4->1->3->6是合法的,因为1->3时点2已经被划过了。

    资源约定:
    峰值内存消耗 < 256M
    CPU消耗 < 1000ms

    某大神已经算出:一共有389112种不同的解锁方案。没有任何线索时,要想暴力解锁确实很难。 不过小Hi很好奇,他希望知道,当已经瞥视到一部分折线的情况下,有多少种不同的方案。 遗憾的是,小Hi看到的部分折线既不一定是连续的,也不知道方向。

    请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
    注意:
    main函数需要返回0;
    只使用ANSI C/ANSI C++ 标准;
    不要调用依赖于编译环境或操作系统的特殊函数。
    所有依赖的函数必须明确地在源文件中 #include
    不能通过工程设置而省略常用头文件。
    提交程序时,注意选择所期望的语言类型和编译器类型。

    例如看到1-2-3和4-5-6, 那么1->2->3->4->5->6,1->2->3->6->5->4, 3->2->1->6->5->4->8->9等都是可能的方案。

    图片 1

    你的任务是编写程序,根据已经瞥到的零碎线段,求可能解锁方案的数目。

    我的解题思路很简单很直白,由于行驶轨迹已经固定,所以只要从原点开始沿着轨迹边走边判断即可。

    输入: 每个测试数据第一行是一个整数N(0 <= N <= 8),代表小Hi看到的折线段数目。 以下N行每行包含两个整数 X 和 Y (1 <= X, Y <= 9),代表小Hi看到点X和点Y是直接相连的。

    分为左/上/右/下四个方向按顺序行走,可以看到先向左1步、上1步、右2步、下2步;

    输出: 对于每组数据输出合法的解锁方案数目。

    然后左3步、上3步、右4步、下4步;以后都是每次+2;我们每走一步就判

    例如: 输入:

    断是否到终点。(代码不够简练,如有错误,很欢迎指正)

    8

      1 #include<stdio.h>  2 #include<math.h>  3   4 int xx[]={-1,0,1,0};    //左上右下  5 int yy[]={0,1,0,-1};  6   7 int count;    //计数器   8   9 int left=1;    //4个方向初值  10 int up=1; 11 int right=2; 12 int down=2; 13  14 int main() 15 { 16     long long x,y; 17     scanf("%I64d%I64d",&x,&y); 18      19     int dx=0; 20     int dy=0; 21     int c=0; 22     int flag=0;    //标志  23      24     if( dx==x && dy==y ) 25     { 26         printf("0"); 27         return 0; 28     } 29         else 30         { 31             int i; 32             for(i=0;i<=3;i++) 33             { 34                 c=0; 35                 if(i==0)    //左 36                 { 37                     while(c<left) 38                     {  39                         dx+=xx[i]; 40                         dy+=yy[i]; 41                         count+=fabs+fabs;    //加步数 42                         if(dx==x && dy==y)    //走了以后判断 43                         {  44                             flag=1; 45                             break; 46                         }  47                         c++; 48                     }  49                     if(flag==1) 50                         break; 51                     left+=2;    //步数+2  52                 } 53                 if(i==1)    //上  54                 { 55                     while(c<up) 56                     {  57                         dx+=xx[i]; 58                         dy+=yy[i]; 59                         count+=fabs+fabs; 60                         if(dx==x && dy==y) 61                         {  62                             flag=1; 63                             break; 64                         }  65                         c++; 66                     } 67                     if(flag==1) 68                         break; 69                     up+=2;  70                 } 71                 if(i==2)    //右  72                 { 73                     while(c<right) 74                     {  75                         dx+=xx[i]; 76                         dy+=yy[i]; 77                         count+=fabs+fabs; 78                         if(dx==x && dy==y) 79                         {  80                             flag=1; 81                             break; 82                         }  83                         c++; 84                     } 85                     if(flag==1) 86                         break; 87                     right+=2;  88                 } 89                 if(i==3)    //下  90                 { 91                     while(c<down) 92                     {  93                         dx+=xx[i]; 94                         dy+=yy[i]; 95                         count+=fabs+fabs; 96                         if(dx==x && dy==y) 97                         {  98                             flag=1; 99                             break;100                         } 101                         c++;102                     }103                     if(flag==1)104                         break;105                     down+=2; 106                 }107                 if(i==3)    //再次相加108                     i=-1;109             }110         }111     printf("%d",count);112     return 0;113 }
    

    1 2
    2 3
    3 4
    4 5
    5 6
    6 7
    7 8
    8 9

    09:49:11

    程序应该输出: 2

    2018-04-10

    再例如: 输入:

    4

    2 4

    2 5

    8 5

    8 6

    程序应该输出: 258

    资源约定: 峰值内存消耗(含虚拟机) < 256M CPU消耗  < 1000ms

    请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

    所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。 java选手注意:不要使用package语句。不要使用jdk1.7及以上版本的特性。 java选手注意:主类的名字必须是:Main,否则按无效代码处理。

    c/c++选手注意: main函数需要返回0 c/c++选手注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。 c/c++选手注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。

    提交程序时,注意选择所期望的语言类型和编译器类型。

     

    注释:思路:直接dfs,需要注意的是去除掉不可行的方法,如1->3就是不可行,因为2之前没有被划到过,因此我创建了isOK函数判断最近选取的两点是否可行,dig数组中[i][j]中j=2时,代表不可行的数值,f数组代表之前这个数是否已经被划中。

     1 /*
     2 测试数据: 
     3 1 2
     4 2 3
     5 3 4
     6 4 5
     7 5 6
     8 6 7
     9 7 8
    10 8 9
    11 */
    12 #include<stdio.h>
    13 #include<stdlib.h> 
    14 #include<string.h>
    15 #include<math.h>
    16 int n;//看到的折线段数目
    17 int path[9][2];//表看到的片段 
    18 int ans=0;
    19 bool use[9];//标记该位置是否滑过 
    20 int hefa(int a,int b){
    21     //枚举出8个非法集合
    22     int feifa[][3]={{1,3,2},{1,7,4},{1,9,5},{2,8,5},{3,7,5},{3,9,6},{4,6,5},{7,9,8}};
    23     for(int i=0;i<8;i++){
    24         if((a==feifa[i][0] && b==feifa[i][1]) || (a==feifa[i][1] && b==feifa[i][0])){
    25             if(!feifa[i][2]){
    26                 return 0;
    27             }
    28         }
    29     }
    30     return 1;
    31 }
    32 void dfs(int number,int begin,int press[]){
    33     //若已经选中2个数字了,判断刚刚选中的两个数字是否合法 
    34     if(begin >= 2){
    35         int a = press[begin-1];
    36         int b = press[begin-2];
    37         if(!hefa(a,b)){
    38             return;
    39         }
    40     }
    41     /*表已经选中的数字达到需要选择的数量(number);
    42      与已看到的片段比较,若刚选中的片段存在于已看到的片段数组中,则继续,否则返回。 
    43     */ 
    44     if(begin==number){
    45         for(int i=0;i<n;i++){
    46             int a = path[i][0];
    47             int b = path[i][1];
    48             for(int j=0;j<=begin-1;j++){
    49                 if((a==press[j] && b==press[j+1]) || (b==press[j] && a==press[j+1])){
    50                     break;
    51                 }
    52                 if(j==begin-2)
    53                     return;
    54             }
    55         }
    56         ans++;
    57         return;
    58     }
    59     else if(begin>number){//选多了 
    60         return;
    61     }
    62     //dfs主体 
    63     for(int i=1;i<=9;i++){
    64         if(!use[i]){
    65             use[i] = true;
    66             press[begin] = i;
    67             dfs(number,begin+1,press);//搜索下一个 
    68             use[i] = false;
    69         }
    70     }
    71 }
    72 int main(){
    73     memset(use,false,sizeof(use));
    74     scanf("%d",&n);
    75     getchar();//处理回车 
    76     int press[10]={0};//存放当前划中数字的数组
    77     for(int i=0;i<n;i++){
    78         scanf("%d%d",&path[i][0],&path[i][1]);
    79     }
    80     for(int i=n>4?n:4; i<=9; i++){
    81         /*参数含义:
    82             i:划中得数字;
    83             0:begin:划得位置,选到第几个了;
    84             press:存放当前划中数字的数组 .
    85         */
    86         dfs(i,0,press);
    87     }
    88     printf("%d",ans);
    89     return 0;
    90 }
    

     

    本文由美高梅网投网址发布于美高梅手机网投,转载请注明出处:对于整点,反复移动到一个尚未经过的"相邻"的点

    关键词: