题解

2 条题解

  • 1
    @ 2018-10-28 10:40:08

    题解 P4205 [NOI2005]智~~障~~慧珠游戏

    小时候,你玩智~~障~~慧珠;长大后,智~~障~~慧珠玩你

    先给大家简述一下题意:(不会玩智障珠游戏的自己去百度一下)

    写一个程序解决骨灰级智障珠问题(只给出\(1\)~\(3\)个块,你需要自己填完剩下的\(9\)~\(11\)块)

    数据保证至多有一组解。

    假装分析一下:这是所有块的形状

    由于图形可以旋转、翻折、~~跳跃~~,所以要先把12个零件的所有形状枚举出来:

    • A:4种
    • B:2种
    • C:8种
    • D:1种
    • E:4种
    • F:8种
    • H:8种
    • I:8种
    • J:1种
    • K:4种
    • L:8种

    总共只有56种情况,如果你觉得多的话请跳过此题解。

    如果你不想用搜索做,请跳过此题解。

    每次从上到下,从做到右找出第一个没有被放零件的格子。56种情况一一枚举就行了(**剪枝想怎么搞怎么搞只要是对的就OK了**)注意回溯。

    听说有个点会卡顺序搜,那么就可以换个方向就行了(**或者卡个搜索次数**)

    ** 代码不长,刚过千行。没有猪国杀的变态,没有mayan游戏的玄学,没有A+B问题的变幻无常,没有任何超纲。阻挡你向前的只是你的懒惰,是你的习得性无助。学OI的意义是什么?成为dalao的意义是什么?只有成为真正的码农,才无愧于你的内心。**

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    
    using namespace std;
    
    char id(int x){
        return (char)(x+'A'-1);
    }
    
    int gi(){
        char x=getchar();
        while(x!='.'&&(x>'Z'||x<'A')) x=getchar();
        return x=='.'?0:(int)(x-'A'+1);
    }
    
    int a[16][16],ti;
    bool in[15];
    
    int get(){
        for(int i=1;i<=10;i++){
            for(int j=1;j<=i;j++)
                 if(a[j][i]==0){
            return j*100+i;
            }
        }
    }
    
    bool ok(){
         for(int o=1;o<=12;o++)
         if(in[o]==false)
         return false;
         return true;
    }
    
    void init(){
        memset(a,-1,sizeof(a));
        memset(in,0,sizeof(in));
        for(int i=1;i<=10;i++){
            for(int j=1;j<=i;j++){
                a[j][i]=gi();
                in[a[j][i]]=true;
            }
        }
        for(int i=1;i<=10;i++){
            for(int j=1;j<=i;j++){
                if(a[j][i]==-1) {
                    a[j][i]=0;
                }
            }
        }
    }
    
    void print(){
        for(int i=1;i<=10;i++){
            for(int j=1;j<=i;j++){
                cout<<id(a[j][i]);  
            }
            cout<<endl;
        }
    }
    
    void dfs(){
        ti++;
        
        if(ti>=3000000){
            printf("No solution");
            exit(0);
        }//卡搜索次数
        //可以玄学证明:如果有解那么深搜的最大次数不会超过3e6
        
        if(ok()) {
          print();
          exit(0);  
        }
          
        int zt=get();
        int px=zt/100;
        int py=zt%10;
        if(py==0) py=10;
        
        //A:4cases
        if(!in[1]){
            
            if(a[px+1][py]==0&&a[px][py+1]==0){
                a[px][py]=1;
                a[px+1][py]=1;
                a[px][py+1]=1;
                in[1]=true;
                 dfs();
                a[px][py]=0;
                a[px+1][py]=0;
                a[px][py+1]=0;
                in[1]=false;
            } 
            
            if(a[px][py+1]==0&&a[px+1][py+1]==0){
                a[px][py]=1;
                a[px][py+1]=1;
                a[px+1][py+1]=1;
                in[1]=true;
                dfs();
                a[px][py]=0;
                a[px][py+1]=0;
                a[px+1][py+1]=0;
                in[1]=false;
            } 
            
            if(a[px][py+1]==0&&a[px-1][py+1]==0){
                a[px][py]=1;
                a[px][py+1]=1;
                a[px-1][py+1]=1;
                in[1]=true;
                dfs();
                a[px][py]=0;
                a[px][py+1]=0;
                a[px-1][py+1]=0;
                in[1]=false;
            } 
            
            if(a[px+1][py]==0&&a[px+1][py+1]==0){
                a[px][py]=1;
                a[px+1][py]=1;
                a[px+1][py+1]=1;
                in[1]=true;
                dfs();
                a[px][py]=0;
                a[px+1][py]=0;
                a[px+1][py+1]=0;
                in[1]=false;
            } 
            
        }
        
        //B:2cases
        if(!in[2]){
            
           if(a[px+1][py]==0&&a[px+2][py]==0&&a[px+3][py]==0){
              a[px][py]=2;
              a[px+1][py]=2;
              a[px+2][py]=2;
              a[px+3][py]=2;
              in[2]=true;
              dfs();
              a[px][py]=0;
              a[px+1][py]=0;
              a[px+2][py]=0;
              a[px+3][py]=0;
              in[2]=false;
           }
           
           if(a[px][py+1]==0&&a[px][py+2]==0&&a[px][py+3]==0){
              a[px][py]=2;
              a[px][py+1]=2;
              a[px][py+2]=2;
              a[px][py+3]=2;
              in[2]=true;
              dfs();
              a[px][py]=0;
              a[px][py+1]=0;
              a[px][py+2]=0;
              a[px][py+3]=0;
              in[2]=false;
           }
           
        }
        
        //C:8cases
        if(!in[3]){
            
           if(a[px+1][py]==0&&a[px+2][py]==0&&a[px][py+1]==0){
               a[px][py]=3;
               a[px+1][py]=3;
               a[px+2][py]=3;
               a[px][py+1]=3;
               in[3]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px+2][py]=0;
               a[px][py+1]=0;
               in[3]=false;
           }
           
           if(a[px+1][py]==0&&a[px+1][py+1]==0&&a[px+1][py+2]==0){
               a[px][py]=3;
               a[px+1][py]=3;
               a[px+1][py+1]=3;
               a[px+1][py+2]=3;
               in[3]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px+1][py+1]=0;
               a[px+1][py+2]=0;
               in[3]=false;
           }
           
           if(a[px+1][py]==0&&a[px][py+1]==0&&a[px][py+2]==0) {
               a[px][py]=3;
               a[px+1][py]=3;
               a[px][py+1]=3;
               a[px][py+2]=3;
               in[3]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               in[3]=false;
           }
           
           if(a[px+1][py]==0&&a[px+2][py]==0&&a[px+2][py+1]==0){
               a[px][py]=3;
               a[px+2][py]=3;
               a[px+2][py+1]=3;
               a[px+1][py]=3;
               in[3]=true;
               dfs();
               a[px][py]=0;
               a[px+2][py]=0;
               a[px+2][py+1]=0;
               a[px+1][py]=0;
               in[3]=false;
           }  
           
           if(a[px+1][py+2]==0&&a[px][py+2]==0&&a[px][py+1]==0){
               a[px][py]=3;
               a[px+1][py+2]=3;
               a[px][py+2]=3;
               a[px][py+1]=3;
               in[3]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py+2]=0;
               a[px][py+2]=0;
               a[px][py+1]=0;
               in[3]=false;
           }
           
           if(a[px-1][py+2]==0&&a[px][py+1]==0&&a[px][py+2]==0) {
               a[px][py]=3;
               a[px-1][py+2]=3;
               a[px][py+1]=3;
               a[px][py+2]=3;
               in[3]=true;
               dfs();
               a[px][py]=0;
               a[px-1][py+2]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               in[3]=false;
           }
           
           if(a[px][py+1]==0&&a[px+1][py+1]==0&&a[px+2][py+1]==0){
               a[px][py]=3;
               a[px][py+1]=3;
               a[px+1][py+1]=3;
               a[px+2][py+1]=3;
               in[3]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px+1][py+1]=0;
               a[px+2][py+1]=0;
               in[3]=false;
           }
           
           if(a[px][py+1]==0&&a[px-1][py+1]==0&&a[px-2][py+1]==0){
               a[px][py]=3;
               a[px][py+1]=3;
               a[px-1][py+1]=3;
               a[px-2][py+1]=3;
               in[3]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px-1][py+1]=0;
               a[px-2][py+1]=0;
               in[3]=false;
           }
           
        }
        
        //D:1case
        if(!in[4]){
            
            if(a[px][py+1]==0&&a[px+1][py+1]==0&&a[px+1][py]==0){
               a[px][py]=4;
               a[px][py+1]=4;
               a[px+1][py+1]=4;
               a[px+1][py]=4;
               in[4]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px+1][py+1]=0;
               a[px+1][py]=0;
               in[4]=false;
            } 
            
        }
        
        //E:4cases
        if(!in[5]){
            
          if(a[px+1][py]==0&&a[px+2][py]==0&&a[px][py+1]==0&&a[px][py+2]==0) {
               a[px][py]=5;
               a[px+1][py]=5;
               a[px+2][py]=5;
               a[px][py+1]=5;
               a[px][py+2]=5;
               in[5]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px+2][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               in[5]=false;
          }
          
          if(a[px+1][py]==0&&a[px+2][py]==0&&a[px][py-1]==0&&a[px][py-2]==0) {
               a[px][py]=5;
               a[px+1][py]=5;
               a[px+2][py]=5;
               a[px][py-1]=5;
               a[px][py-2]=5;
               in[5]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px+2][py]=0;
               a[px][py-1]=0;
               a[px][py-2]=0;
               in[5]=false;
          }
          
          if(a[px][py+1]==0&&a[px][py+2]==0&&a[px+1][py+2]==0&&a[px+2][py+2]==0){
               a[px][py]=5;
               a[px][py+1]=5;
               a[px][py+2]=5;
               a[px+1][py+2]=5;
               a[px+2][py+2]=5;
               in[5]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px+1][py+2]=0;
               a[px+2][py+2]=0;
               in[5]=false;
          }
          
          if(a[px][py+1]==0&&a[px][py+2]==0&&a[px-1][py+2]==0&&a[px-2][py+2]==0){
               a[px][py]=5;
               a[px][py+1]=5;
               a[px][py+2]=5;
               a[px-1][py+2]=5;
               a[px-2][py+2]=5;
               in[5]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px-1][py+2]=0;
               a[px-2][py+2]=0;
               in[5]=false;
          }
          
        }
        
        //F:8cases
        if(!in[6]){
            
           if(a[px-1][py+1]==0&&a[px][py+1]==0&&a[px+1][py+1]==0&&a[px+2][py+1]==0){
               a[px][py]=6;
               a[px-1][py+1]=6;
               a[px][py+1]=6;
               a[px+1][py+1]=6;
               a[px+2][py+1]=6;
               in[6]=true;
               dfs();
               a[px][py]=0;
               a[px-1][py+1]=0;
               a[px][py+1]=0;
               a[px+1][py+1]=0;
               a[px+2][py+1]=0;
               in[6]=false;
        } 
        
           if(a[px-1][py+1]==0&&a[px][py+1]==0&&a[px+1][py+1]==0&&a[px-2][py+1]==0) {
               a[px][py]=6;
               a[px-1][py+1]=6;
               a[px][py+1]=6;
               a[px+1][py+1]=6;
               a[px-2][py+1]=6;
               in[6]=true;
               dfs();
               a[px][py]=0;
               a[px-1][py+1]=0;
               a[px][py+1]=0;
               a[px+1][py+1]=0;
               a[px-2][py+1]=0;
               in[6]=false;
        }
        
           if(a[px+1][py+1]==0&&a[px+1][py]==0&&a[px+2][py]==0&&a[px+3][py]==0) {
               a[px][py]=6;
               a[px+1][py+1]=6;
               a[px+1][py]=6;
               a[px+2][py]=6;
               a[px+3][py]=6;
               in[6]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py+1]=0;
               a[px+1][py]=0;
               a[px+2][py]=0;
               a[px+3][py]=0;
               in[6]=false;
        }
        
           if(a[px+1][py]==0&&a[px+2][py+1]==0&&a[px+2][py]==0&&a[px+3][py]==0) {
               a[px][py]=6;
               a[px+1][py]=6;
               a[px+2][py+1]=6;
               a[px+2][py]=6;
               a[px+3][py]=6;
               in[6]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px+2][py+1]=0;
               a[px+2][py]=0;
               a[px+3][py]=0;
               in[6]=false;
        }
        
           if(a[px][py+1]==0&&a[px][py+2]==0&&a[px][py+3]==0&&a[px+1][py+1]==0){
               a[px][py]=6;
               a[px][py+1]=6;
               a[px][py+2]=6;
               a[px][py+3]=6;
               a[px+1][py+1]=6;
               in[6]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px][py+3]=0;
               a[px+1][py+1]=0;
               in[6]=false;
        } 
        
           if(a[px][py+1]==0&&a[px][py+2]==0&&a[px][py+3]==0&&a[px-1][py+1]==0) {
               a[px][py]=6;
               a[px][py+1]=6;
               a[px][py+2]=6;
               a[px][py+3]=6;
               a[px-1][py+1]=6;
               in[6]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px][py+3]=0;
               a[px-1][py+1]=0;
               in[6]=false;
        }
        
           if(a[px][py+1]==0&&a[px][py+2]==0&&a[px][py+3]==0&&a[px+1][py+2]==0) {
               a[px][py]=6;
               a[px][py+1]=6;
               a[px][py+2]=6;
               a[px][py+3]=6;
               a[px+1][py+2]=6;
               in[6]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px][py+3]=0;
               a[px+1][py+2]=0;
               in[6]=false;
        }
        
           if(a[px][py+1]==0&&a[px][py+2]==0&&a[px][py+3]==0&&a[px-1][py+2]==0) {
               a[px][py]=6;
               a[px][py+1]=6;
               a[px][py+2]=6;
               a[px][py+3]=6;
               a[px-1][py+2]=6;
               in[6]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px][py+3]=0;
               a[px-1][py+2]=0;
               in[6]=false;
           }
        }
        
        //G:4cases
        if(!in[7]){
            
           if(a[px][py+1]==0&&a[px+1][py]==0&&a[px+2][py+1]==0&&a[px+2][py]==0) {
               a[px][py]=7;
               a[px][py+1]=7;
               a[px+1][py]=7;
               a[px+2][py+1]=7;
               a[px+2][py]=7;
               in[7]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px+1][py]=0;
               a[px+2][py+1]=0;
               a[px+2][py]=0;
               in[7]=false;
           }
           
           if(a[px][py+1]==0&&a[px+1][py+1]==0&&a[px+2][py+1]==0&&a[px+2][py]==0) {
               a[px][py]=7;
               a[px][py+1]=7;
               a[px+1][py+1]=7;
               a[px+2][py+1]=7;
               a[px+2][py]=7;
               in[7]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px+1][py+1]=0;
               a[px+2][py+1]=0;
               a[px+2][py]=0;
               in[7]=false;
           }
           
           if(a[px][py+1]==0&&a[px][py+2]==0&&a[px+1][py+2]==0&&a[px+1][py]==0) {
               a[px][py]=7;
               a[px][py+1]=7;
               a[px][py+2]=7;
               a[px+1][py+2]=7;
               a[px+1][py]=7;
               in[7]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px+1][py+2]=0;
               a[px+1][py]=0;
               in[7]=false;
           }
           
           if(a[px+1][py]==0&&a[px+1][py+1]==0&&a[px+1][py+2]==0&&a[px][py+2]==0) {
               a[px][py]=7;
               a[px+1][py]=7;
               a[px+1][py+1]=7;
               a[px+1][py+2]=7;
               a[px][py+2]=7;
               in[7]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px+1][py+1]=0;
               a[px+1][py+2]=0;
               a[px][py+2]=0;
               in[7]=false;
           }
           
        }
        
        //H:8cases
        if(!in[8]){
            
        if(a[px+1][py]==0&&a[px+1][py+1]==0&&a[px+2][py]==0&&a[px+2][py+1]==0) {
               a[px][py]=8;
               a[px+1][py]=8;
               a[px+1][py+1]=8;
               a[px+2][py]=8;
               a[px+2][py+1]=8;
               in[8]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px+1][py+1]=0;
               a[px+2][py]=0;
               a[px+2][py+1]=0;
               in[8]=false;
        }
        
          if(a[px-1][py+1]==0&&a[px][py+1]==0&&a[px+1][py+1]==0&&a[px+1][py]==0) {
               a[px][py]=8;
               a[px-1][py+1]=8;
               a[px][py+1]=8;
               a[px+1][py+1]=8;
               a[px+1][py]=8;
               in[8]=true;
               dfs();
               a[px][py]=0;
               a[px-1][py+1]=0;
               a[px][py+1]=0;
               a[px+1][py+1]=0;
               a[px+1][py]=0;
               in[8]=false;
        }
        
          if(a[px][py+1]==0&&a[px+1][py]==0&&a[px+1][py+1]==0&&a[px+2][py+1]==0) {
               a[px][py]=8;
               a[px+1][py]=8;
               a[px][py+1]=8;
               a[px+1][py+1]=8;
               a[px+2][py+1]=8;
               in[8]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px][py+1]=0;
               a[px+1][py+1]=0;
               a[px+2][py+1]=0;
               in[8]=false;
        }
        
          if(a[px+1][py]==0&&a[px+2][py]==0&&a[px][py+1]==0&&a[px+1][py+1]==0){
               a[px][py]=8;
               a[px+1][py]=8;
               a[px+2][py]=8;
               a[px][py+1]=8;
               a[px+1][py+1]=8;
               in[8]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px+2][py]=0;
               a[px][py+1]=0;
               a[px+1][py+1]=0;
               in[8]=false;
        } 
        
          if(a[px][py+1]==0&&a[px][py+2]==0&&a[px+1][py+1]==0&&a[px+1][py+2]==0) {
               a[px][py]=8;
               a[px][py+1]=8;
               a[px][py+2]=8;
               a[px+1][py+1]=8;
               a[px+1][py+2]=8;
               in[8]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px+1][py+1]=0;
               a[px+1][py+2]=0;
               in[8]=false;
        }
        
          if(a[px][py+1]==0&&a[px][py+2]==0&&a[px-1][py+1]==0&&a[px-1][py+2]==0){
               a[px][py]=8;
               a[px][py+1]=8;
               a[px][py+2]=8;
               a[px-1][py+1]=8;
               a[px-1][py+2]=8;
               in[8]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px-1][py+1]=0;
               a[px-1][py+2]=0;
               in[8]=false;
        }
        
          if(a[px][py+1]==0&&a[px][py+2]==0&&a[px+1][py]==0&&a[px+1][py+1]==0) {
               a[px][py]=8;
               a[px][py+1]=8;
               a[px][py+2]=8;
               a[px+1][py]=8;
               a[px+1][py+1]=8;
               in[8]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px+1][py]=0;
               a[px+1][py+1]=0;
               in[8]=false;
        }
        
          if(a[px][py+1]==0&&a[px+1][py+2]==0&&a[px+1][py+1]==0&&a[px+1][py]==0){
               a[px][py]=8;
               a[px][py+1]=8;
               a[px+1][py+2]=8;
               a[px+1][py+1]=8;
               a[px+1][py]=8;
               in[8]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px+1][py+2]=0;
               a[px+1][py+1]=0;
               a[px+1][py]=0;
               in[8]=false;
           } 
        }
        
        //I:8cases
        if(!in[9]){
            
          if(a[px+1][py]==0&&a[px+2][py]==0&&a[px+2][py+1]==0&&a[px+3][py+1]==0){
               a[px][py]=9;
               a[px+1][py]=9;
               a[px+2][py]=9;
               a[px+2][py+1]=9;
               a[px+3][py+1]=9;
               in[9]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px+2][py]=0;
               a[px+2][py+1]=0;
               a[px+3][py+1]=0;
               in[9]=false;
        }
        
          if(a[px-2][py+1]==0&&a[px-1][py+1]==0&&a[px][py+1]==0&&a[px+1][py]==0) {
               a[px][py]=9;
               a[px-2][py+1]=9;
               a[px-1][py+1]=9;
               a[px][py+1]=9;
               a[px+1][py]=9;
               in[9]=true;
               dfs();
               a[px][py]=0;
               a[px-2][py+1]=0;
               a[px-1][py+1]=0;
               a[px][py+1]=0;
               a[px+1][py]=0;
               in[9]=false;
        }
        
          if(a[px+1][py]==0&&a[px+1][py+1]==0&&a[px+2][py+1]==0&&a[px+3][py+1]==0){
               a[px][py]=9;
               a[px+1][py]=9;
               a[px+1][py+1]=9;
               a[px+2][py+1]=9;
               a[px+3][py+1]=9;
               in[9]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px+1][py+1]=0;
               a[px+2][py+1]=0;
               a[px+3][py+1]=0;
               in[9]=false;
        } 
        
          if(a[px][py+1]==0&&a[px-1][py+1]==0&&a[px-2][py+1]==0&&a[px+1][py]==0){
               a[px][py]=9;
               a[px][py+1]=9;
               a[px-1][py+1]=9;
               a[px-2][py+1]=9;
               a[px+1][py]=9;
               in[9]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px-1][py+1]=0;
               a[px-2][py+1]=0;
               a[px+1][py]=0;
               in[9]=false;
        } 
        
          if(a[px][py+1]==0&&a[px+1][py+1]==0&&a[px+1][py+3]==0&&a[px+1][py+2]==0){
               a[px][py]=9;
               a[px][py+1]=9;
               a[px+1][py+1]=9;
               a[px+1][py+3]=9;
               a[px+1][py+2]=9;
               in[9]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px+1][py+1]=0;
               a[px+1][py+3]=0;
               a[px+1][py+2]=0;
               in[9]=false;
        }
        
          if(a[px][py+1]==0&&a[px-1][py+1]==0&&a[px-1][py+3]==0&&a[px-1][py+2]==0){
               a[px][py]=9;
               a[px][py+1]=9;
               a[px-1][py+1]=9;
               a[px-1][py+3]=9;
               a[px-1][py+2]=9;
               in[9]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px-1][py+1]=0;
               a[px-1][py+3]=0;
               a[px-1][py+2]=0;
               in[9]=false;
        }
        
          if(a[px][py+1]==0&&a[px][py+2]==0&&a[px+1][py+2]==0&&a[px+1][py+3]==0) {
               a[px][py]=9;
               a[px][py+1]=9;
               a[px][py+2]=9;
               a[px+1][py+2]=9;
               a[px+1][py+3]=9;
               in[9]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px+1][py+2]=0;
               a[px+1][py+3]=0;
               in[9]=false;
        }
        
          if(a[px][py+1]==0&&a[px][py+2]==0&&a[px-1][py+2]==0&&a[px-1][py+3]==0) {
               a[px][py]=9;
               a[px][py+1]=9;
               a[px][py+2]=9;
               a[px-1][py+2]=9;
               a[px-1][py+3]=9;
               in[9]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px-1][py+2]=0;
               a[px-1][py+3]=0;
               in[9]=false;
           }
           
        }
        
        //J:1case
        if(!in[10]){
            
          if(a[px][py+1]==0&&a[px][py+2]==0&&a[px-1][py+1]==0&&a[px+1][py+1]==0) {
               a[px][py]=10;
               a[px][py+1]=10;
               a[px][py+2]=10;
               a[px-1][py+1]=10;
               a[px+1][py+1]=10;
               in[10]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px-1][py+1]=0;
               a[px+1][py+1]=0;
               in[10]=false;
          }
          
        }
        
        //K:4cases
        if(!in[11]){
            
          if(a[px][py+1]==0&&a[px+1][py+1]==0&&a[px+1][py+2]==0&&a[px+2][py+2]==0) {
               a[px][py]=11;
               a[px][py+1]=11;
               a[px+1][py+1]=11;
               a[px+1][py+2]=11;
               a[px+2][py+2]=11;
               in[11]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px+1][py+1]=0;
               a[px+1][py+2]=0;
               a[px+2][py+2]=0;
               in[11]=false;
        }
        
          if(a[px][py+1]==0&&a[px-1][py+1]==0&&a[px-1][py+2]==0&&a[px-2][py+2]==0) {
               a[px][py]=11;
               a[px][py+1]=11;
               a[px-1][py+1]=11;
               a[px-1][py+2]=11;
               a[px-2][py+2]=11;
               in[11]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px-1][py+1]=0;
               a[px-1][py+2]=0;
               a[px-2][py+2]=0;
               in[11]=false;
        }
        
          if(a[px+1][py]==0&&a[px+1][py+1]==0&&a[px+2][py+1]==0&&a[px+2][py+2]==0){
               a[px][py]=11;
               a[px+1][py]=11;
               a[px+1][py+1]=11;
               a[px+2][py+1]=11;
               a[px+2][py+2]=11;
               in[11]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px+1][py+1]=0;
               a[px+2][py+1]=0;
               a[px+2][py+2]=0;
               in[11]=false;
        }
        
          if(a[px+1][py]==0&&a[px][py+1]==0&&a[px-1][py+1]==0&&a[px-1][py+2]==0){
               a[px][py]=11;
               a[px][py+1]=11;
               a[px+1][py]=11;
               a[px-1][py+1]=11;
               a[px-1][py+2]=11;
               in[11]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px+1][py]=0;
               a[px-1][py+1]=0;
               a[px-1][py+2]=0;
               in[11]=false;
           }
           
        }
        
        //L:8cases
        if(!in[12]){
            
          if(a[px][py+1]==0&&a[px+1][py]==0&&a[px+2][py]==0&&a[px+3][py]==0) {
               a[px][py]=12;
               a[px][py+1]=12;
               a[px+1][py]=12;
               a[px+2][py]=12;
               a[px+3][py]=12;
               in[12]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px+1][py]=0;
               a[px+2][py]=0;
               a[px+3][py]=0;
               in[12]=false;
        }
        
          if(a[px+3][py+1]==0&&a[px+1][py]==0&&a[px+2][py]==0&&a[px+3][py]==0){
               a[px][py]=12;
               a[px+3][py+1]=12;
               a[px+1][py]=12;
               a[px+2][py]=12;
               a[px+3][py]=12;
               in[12]=true;
               dfs();
               a[px][py]=0;
               a[px+3][py+1]=0;
               a[px+1][py]=0;
               a[px+2][py]=0;
               a[px+3][py]=0;
               in[12]=false;
        } 
        
          if(a[px][py+1]==0&&a[px+1][py+1]==0&&a[px+2][py+1]==0&&a[px+3][py+1]==0){
               a[px][py]=12;
               a[px][py+1]=12;
               a[px+1][py+1]=12;
               a[px+2][py+1]=12;
               a[px+3][py+1]=12;
               in[12]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px+1][py+1]=0;
               a[px+2][py+1]=0;
               a[px+3][py+1]=0;
               in[12]=false;
        } 
        
          if(a[px][py+1]==0&&a[px-1][py+1]==0&&a[px-2][py+1]==0&&a[px-3][py+1]==0){
               a[px][py]=12;
               a[px][py+1]=12;
               a[px-1][py+1]=12;
               a[px-2][py+1]=12;
               a[px-3][py+1]=12;
               in[12]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px-1][py+1]=0;
               a[px-2][py+1]=0;
               a[px-3][py+1]=0;
               in[12]=false;
        }
        
          if(a[px+1][py]==0&&a[px+1][py+1]==0&&a[px+1][py+2]==0&&a[px+1][py+3]==0) {
               a[px][py]=12;
               a[px+1][py]=12;
               a[px+1][py+1]=12;
               a[px+1][py+2]=12;
               a[px+1][py+3]=12;
               in[12]=true;
               dfs();
               a[px][py]=0;
               a[px+1][py]=0;
               a[px+1][py+1]=0;
               a[px+1][py+2]=0;
               a[px+1][py+3]=0;
               in[12]=false;
        }
        
          if(a[px+1][py]==0&&a[px][py+1]==0&&a[px][py+2]==0&&a[px][py+3]==0){
               a[px][py]=12;
               a[px][py+1]=12;
               a[px+1][py]=12;
               a[px][py+2]=12;
               a[px][py+3]=12;
               in[12]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px+1][py]=0;
               a[px][py+2]=0;
               a[px][py+3]=0;
               in[12]=false;
        } 
        
          if(a[px][py+1]==0&&a[px][py+2]==0&&a[px][py+3]==0&&a[px+1][py+3]==0) {
               a[px][py]=12;
               a[px][py+1]=12;
               a[px][py+2]=12;
               a[px][py+3]=12;
               a[px+1][py+3]=12;
               in[12]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px][py+3]=0;
               a[px+1][py+3]=0;
               in[12]=false;
        }
        
          if(a[px][py+1]==0&&a[px][py+2]==0&&a[px][py+3]==0&&a[px-1][py+3]==0) {
               a[px][py]=12;
               a[px][py+1]=12;
               a[px][py+2]=12;
               a[px][py+3]=12;
               a[px-1][py+3]=12;
               in[12]=true;
               dfs();
               a[px][py]=0;
               a[px][py+1]=0;
               a[px][py+2]=0;
               a[px][py+3]=0;
               a[px-1][py+3]=0;
               in[12]=false;
           }
           
        }
        
    }
    
    void openfile(){
        freopen("game.in","r",stdin);
        freopen("game.out","w",stdout);
    }
    
    int main(){
        //openfile();
        init();
        dfs();
        printf("No solution");
        return 0;
    }
    

    恭喜你彻底农烂

  • 0
    @ 2014-02-05 16:32:04

    program ex3;
    type fan=array[1..5,1..2] of longint;
    const
    len:array[1..12] of longint=(3,4,4,4,5,5,5,5,5,5,5,5);
    wk:array[1..12] of fan=
    (((0,0),(1,0),(0,1),(0,0),(0,0)),
    ((0,0),(1,0),(2,0),(3,0),(0,0)),
    ((0,0),(1,0),(2,0),(0,1),(0,0)),
    ((0,0),(1,0),(0,1),(1,1),(0,0)),
    ((0,0),(1,0),(2,0),(0,1),(0,2)),
    ((0,0),(1,0),(2,0),(3,0),(1,1)),
    ((0,0),(1,0),(2,0),(2,1),(0,1)),
    ((0,0),(1,0),(2,0),(0,1),(1,1)),
    ((0,0),(1,0),(2,0),(2,1),(3,1)),
    ((0,0),(1,0),(2,0),(1,1),(1,-1)),
    ((0,0),(0,1),(1,1),(1,2),(2,2)),
    ((0,0),(1,0),(2,0),(3,0),(0,1)));
    var
    tak:array[0..100] of fan;
    lv:array[0..20] of boolean;
    ln:array[0..100] of longint;
    map,num:array[0..15,0..15] of longint;
    u,d,l,r,tt,tx,ty,size,h:array[0..100000] of longint;
    i,j,k,tot,x,y,xx,yy,t,now:longint; p:char;

    procedure print;var i,j:longint;
    begin
    for i:=1 to 10 do begin
    for j:=1 to i do write(chr(map[i,j]+64));
    writeln;
    end;
    close(input);close(output);halt;
    end;

    procedure rorate(var a,b:fan);var i:longint;
    begin
    for i:=1 to 5 do begin
    b[i,1]:=a[i,2];
    b[i,2]:=-a[i,1];
    end;
    end;

    procedure rev(var a,b:fan);var i:longint;
    begin
    for i:=1 to 5 do begin
    b[i,1]:=a[i,1];
    b[i,2]:=-a[i,2];
    end;
    end;

    function ck(x,y,n:longint):boolean;var i:longint;
    begin
    for i:=1 to len[ln[n]] do
    if map[x+tak[n,i,1],y+tak[n,i,2]]<>0 then exit(false);
    ck:=true;
    end;

    procedure cover(i:longint);var j,k:longint;
    begin
    l[r[i]]:=l[i];r[l[i]]:=r[i];
    j:=d[i];
    while i<>j do begin
    k:=r[j];
    while k<>j do begin
    u[d[k]]:=u[k];d[u[k]]:=d[k];
    dec(size[h[k]]); k:=r[k];
    end;
    j:=d[j];
    end;
    end;

    procedure recover(i:longint);var j,k:longint;
    begin
    l[r[i]]:=i;r[l[i]]:=i;
    j:=u[i];
    while i<>j do begin
    k:=l[j];
    while k<>j do begin
    u[d[k]]:=k;d[u[k]]:=k;
    inc(size[h[k]]); k:=l[k];
    end;
    j:=u[j];
    end;
    end;

    procedure DLX;var i,j,k,min:longint;
    begin
    i:=r[0];min:=maxlongint;
    while i<>0 do begin
    if size[i]<min then begin
    min:=size[i];j:=i;
    end;
    i:=r[i];
    end;
    if min=maxlongint then print;
    if min=0 then exit;
    cover(j); i:=d[j];
    while i<>j do begin
    k:=r[i];
    map[tx[i],ty[i]]:=tt[i];
    while k<>i do begin
    cover(h[k]);
    map[tx[k],ty[k]]:=tt[k];
    k:=r[k];
    end;
    DLX;
    k:=l[i];
    map[tx[i],ty[i]]:=0;
    while k<>i do begin
    recover(h[k]);
    map[tx[k],ty[k]]:=0;
    k:=l[k];
    end;
    i:=d[i];
    end;
    recover(j);
    end;

    begin
    fillchar(map,sizeof(map),$ff);
    for i:=1 to 10 do begin
    for j:=1 to i do begin
    read(p); map[i,j]:=0;
    if p in ['A'..'Z'] then begin
    map[i,j]:=ord(p)-64;
    lv[map[i,j]]:=true;
    end;
    if map[i,j]=0 then begin
    inc(tot);num[i,j]:=tot;
    l[tot]:=tot-1;r[tot-1]:=tot;
    u[tot]:=tot;d[tot]:=tot;h[tot]:=tot;
    end;
    end;readln
    end;
    for i:=1 to 12 do
    if not lv[i] then begin
    inc(tot); num[i,0]:=tot;
    l[tot]:=tot-1;r[tot-1]:=tot;
    u[tot]:=tot;d[tot]:=tot;h[tot]:=tot;
    inc(t);ln[t]:=i;tak[t]:=wk[i];
    if (i=4) or (i=10) then continue;
    inc(t);rorate(tak[t-1],tak[t]);ln[t]:=i;
    if i=2 then continue;
    inc(t);rorate(tak[t-1],tak[t]);ln[t]:=i;
    inc(t);rorate(tak[t-1],tak[t]);ln[t]:=i;
    if (i=10) or (i=7) or (i=5) or (i=1) then continue;
    inc(t);rev(tak[t-1],tak[t]);ln[t]:=i;
    inc(t);rorate(tak[t-1],tak[t]);ln[t]:=i;
    inc(t);rorate(tak[t-1],tak[t]);ln[t]:=i;
    inc(t);rorate(tak[t-1],tak[t]);ln[t]:=i;
    end;
    l[0]:=tot;
    for i:=1 to t do
    for x:=1 to 10 do
    for y:=1 to x do if ck(x,y,i) then begin
    inc(tot);l[tot]:=tot;r[tot]:=tot;
    u[tot]:=u[num[ln[i],0]];d[tot]:=h[u[tot]];
    d[u[tot]]:=tot;u[d[tot]]:=tot;
    now:=tot;h[now]:=h[u[now]];
    inc(size[h[tot]]);
    for j:=1 to len[ln[i]] do begin
    xx:=x+tak[i,j,1];yy:=y+tak[i,j,2];
    inc(tot);l[tot]:=now;r[tot]:=r[now];
    now:=tot;h[tot]:=num[xx,yy];
    d[tot]:=h[tot];u[tot]:=u[h[tot]];
    l[r[tot]]:=tot;r[l[tot]]:=tot;
    d[u[tot]]:=tot;u[d[tot]]:=tot;
    inc(size[h[tot]]);
    tx[tot]:=xx;ty[tot]:=yy;tt[tot]:=ln[i];
    end;
    end;
    DLX;
    writeln('No solution');
    close(input);close(output);
    end.

  • 1

信息

ID
1838
难度
1
分类
(无)
标签
递交数
34
已通过
25
通过率
74%
被复制
2
上传者