hdu 3278  Puzzle

题目来源：

题目大意：给一个4*6的网格，用3中颜色进行涂抹， 每种颜色涂8个小方格，问至少要经过多少步的移动使中间的8个小方格的颜色相同。

思路：猛一看和 hdu的1667很像 ，不过那题状态少，这题状态稍微多一点， 如果数据量很大的话 用IDA*会超时的。。

预处理相对来说是一个很不错的方法， 假定W是最终在中间位置的颜色，那么就把G和B当作同一种颜色，这样就可以通过二进制压缩把状态用一个整形数字表示，

预处理出所有状态之后取三种颜色的最小值即可。

这里需要开2kw的数组，看大牛的博客，需要用char型的。。

代码很龊，2s+，差点就tle了，估计是我参数传递的时候太浪费时间了。。

 

hdu 3567  Eight II

题目来源：

八数码的加强版，问你从一种状态怎样到达另外一种状态。

双广的话应该可以处理，不过处理起来会灰常的麻烦的，因为他要求的是字典序最小的，，用双向广搜需要先找到中间的节点，然后前一段能保证字典序最小，

后一段还要从该中间节点 再搜一次。我写了下，wa了，就没再搞了，太繁琐了。。。

这题也可以用预处理，因为对于任何起始串 12X453786 都可以转化成12X345678，注意X的位置不能改变，然后把目标串相应的改变。

这里就可以先预处理12345678X （X有9个位置）能达到的所有状态，记录路径。

然后对于每个输入的数据直接常数时间输出！

code:

1 # include
      
          2 # include
       
           3 # include
        
            4 # include
         
             5 using namespace std;   6 int dir[9]={
     1,1,2,6,24,120,720,5040,40320};   7 int visit[10][363000],pre[10][363000];   8 int hash(int s[])   9 {
      10     int i,j,sum,cnt;  11     sum=0;  12     for(i=1;i<=9;i++)  13     {
      14         cnt=0;  15         for(j=1;j
          
           s[i]) cnt++;  17         sum+=cnt*dir[i-1];  18     }  19     return sum;  20 }  21 struct node{
      22     int ma[10];  23     int ans,x;  24 };  25 void bfs(int v)  26 {
      27     queue
           
            q; 28 node cur,next; 29 int i,ans; 30 for(i=1;i<=9;i++) 31 { 32 if(i
            
             =0;i--) 138 { 139 if(ch[i]==1) printf("d"); 140 else if(ch[i]==2) printf("l"); 141 else if(ch[i]==3) printf("r"); 142 else if(ch[i]==4) printf("u"); 143 } 144 puts(""); 145 } 146 return 0; 147 }
            
           
          
         
        
       
      

hdu 1430  魔版

题目链接：

做了上面一道题，这道题做起来就很简单了，也是预处理，每一个起始串都能转化成12345678，然后相应的改变目标串，还是求12345678能到达的所有串。。

1 # include
      
          2 # include
       
           3 # include
        
            4 using namespace std;   5 int visit[41000];   6 int pre[41000];   7 int dir[8]={
     1,1,2,6,24,120,720,5040};   8 struct node{
       9     int num;  10     int step;  11 };  12 int hash(int ans)  13 {
      14     int a[9],i,j,sum,cnt;  15     for(i=8;i>=1;i--)  16     {
      17         a[i]=ans%10;  18         ans/=10;  19     }  20     sum=0;  21     for(i=1;i<=8;i++)  22     {
      23         cnt=0;  24         for(j=1;j
         
          a[i]) cnt++;  26             sum+=cnt*dir[i-1];  27     }  28     return sum;  29 }  30 void bfs()  31 {
      32     queue
          
           q;  33     node cur,next;  34     int i,tmp,ans,flag,a[9];  35     cur.num=12345678;  36     cur.step=0;  37     q.push(cur);  38     while(!q.empty())  39     {
      40         cur=q.front();  41         q.pop();  42         ans=cur.num;  43             for(i=8;i>=1;i--)  44             {
      45                 a[i]=ans%10;  46                 ans/=10;  47             };  48             ans=0;  49             for(i=8;i>=1;i--)  50             {
      51                 ans*=10;  52                 ans+=a[i];  53             }  54             flag=hash(ans);  55             if(visit[flag]==0)  56             {
      57                 next.num=ans;  58                 next.step=cur.step+1;  59                 visit[flag]=1;  60                 pre[flag]=hash(cur.num);  61                 q.push(next);  62             }  63             ans=cur.num;  64             for(i=8;i>=1;i--)  65             {
      66                 a[i]=ans%10;  67                 ans/=10;  68             }  69             tmp=a[4];  70             for(i=3;i>=1;i--)  71                 a[i+1]=a[i];  72             a[1]=tmp;  73             tmp=a[5];  74             for(i=6;i<=8;i++)  75                 a[i-1]=a[i];  76             a[8]=tmp;  77             ans=0;  78             for(i=1;i<=8;i++)  79             {
      80                 ans*=10;  81                 ans+=a[i];  82             }  83             flag=hash(ans);  84             if(visit[flag]==0)  85             {
      86                 visit[flag]=2;  87                 next.num=ans;  88                 next.step=cur.step+1;  89                 pre[flag]=hash(cur.num);  90                 q.push(next);  91             }  92              93             ans=cur.num;  94             for(i=8;i>=1;i--)  95             {
      96                 a[i]=ans%10;  97                 ans/=10;  98             }  99             tmp=a[2]; 100             a[2]=a[7];a[7]=a[6]; 101             a[6]=a[3];a[3]=tmp; 102             ans=0; 103             for(i=1;i<=8;i++) 104             {
     105                 ans*=10; 106                 ans+=a[i]; 107             } 108             flag=hash(ans); 109             if(visit[flag]==0) 110             {
     111                 visit[flag]=3;    112                 pre[flag]=hash(cur.num); 113                 next.num=ans; 114                 next.step=cur.step+1; 115                 q.push(next); 116             } 117 118     } 119 } 120 int main() 121 {
     122     int i,j,end,st,a[9],b[9],ans,ch[205]; 123     memset(visit,0,sizeof(visit)); 124     bfs(); 125     while(scanf("%d%d",&st,&end)!=EOF) 126     {
     127         for(i=8;i>=1;i--) 128         {
     129             ans=st%10; 130             a[ans]=i; 131             st/=10; 132         } 133         for(i=8;i>=1;i--) 134         {
     135             b[i]=end%10; 136             b[i]=a[b[i]]; 137             end/=10; 138         } 139         end=0; 140         for(i=1;i<=8;i++) 141         {
     142             end*=10; 143             end+=b[i]; 144         } 145         end=hash(end); 146         j=0; 147         while(end!=0) 148         {
     149             ch[j++]=visit[end]; 150             end=pre[end]; 151         } 152         for(i=j-1;i>=0;i--) 153             printf("%c",ch[i]+'A'-1); 154         puts(""); 155     } 156     return 0; 157 }
          
         
        
       
      

hdu 1401 Solitaire

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1401

比较水的一题，可以开一个四维的数组进行标记，用bool的话不会超内存。。

单广也能过500ms，  第一次写双广，写的比较龊， 125ms。。

发code纪念下：

1 # include
      
          2 # include
       
           3 # include
        
            4 # include
         
             5 using namespace std;   6 bool visit1[62][63][64][65];   7 bool visit2[62][63][64][65];   8 int st[5],end[5];   9 int dir[4][2]={
     0,1,0,-1,1,0,-1,0};  10 struct node{
      11     int s[5];  12     int step;  13 };  14 int cmp1(const void *a,const void *b)  15 {
      16     return *(int *)a - *(int *)b;  17 }  18     queue
          
           q1;  19     queue
           
            q2; 20 bool bfs() 21 { 22 23 node cur1,cur2,next,cur; 24 int i,j,k,i1,ansx,ansy,endx,endy; 25 while(!q1.empty()) q1.pop(); 26 while(!q2.empty()) q2.pop(); 27 int a[5]; 28 for(i=1;i<=4;i++) 29 cur1.s[i]=st[i]; 30 cur1.step=0; 31 visit1[st[1]][st[2]][st[3]][st[4]]=1; 32 if(st[1]==end[1]&&st[2]==end[2] && st[3]==end[3] && st[4]==end[4]) return 1; 33 q1.push(cur1); 34 for(i=1;i<=4;i++) 35 cur2.s[i]=end[i]; 36 cur2.step=0; 37 visit2[end[1]][end[2]][end[3]][end[4]]=1; 38 q2.push(cur2); 39 int ncase=-1; 40 while(1) 41 { 42 ncase++; 43 while(1) 44 { 45 cur=q1.front(); 46 q1.pop(); 47 if(cur.step>ncase) {q1.push(cur);break;} 48 if(cur.step==4) return 0; 49 for(i=0;i<4;i++) 50 { 51 for(j=1;j<=4;j++) 52 { 53 ansx=(cur.s[j]+7)/8; 54 ansy=cur.s[j]-(ansx-1)*8; 55 endx=ansx+dir[i][0]; 56 endy=ansy+dir[i][1]; 57 if(endx<=0 || endx>8||endy<=0 || endy>8) continue; 58 for(k=1;k<=4;k++) 59 if((endx-1)*8+endy == cur.s[k]) break; ///相邻的位置是否已占 60 if(k==5) 61 { 62 for(i1=1;i1<=4;i1++) 63 a[i1]=cur.s[i1]; 64 a[j]=(endx-1)*8+endy; 65 qsort(a+1,4,sizeof(a[1]),cmp1); 66 if(!visit1[a[1]][a[2]][a[3]][a[4]]) 67 { 68 if(visit2[a[1]][a[2]][a[3]][a[4]]!=0) return 1; 69 visit1[a[1]][a[2]][a[3]][a[4]]=1; 70 next.step=cur.step+1; 71 for(i1=1;i1<=4;i1++) 72 next.s[i1]=a[i1]; 73 q1.push(next); 74 } 75 } 76 else 77 { 78 endx+=dir[i][0]; 79 endy+=dir[i][1]; 80 if(endx<=0 || endx>8 || endy<=0 || endy>8) continue; 81 for(i1=1;i1<=4;i1++) 82 if((endx-1)*8+endy==cur.s[i1]) break; 83 if(i1<=4) continue;//能否跳一个格 84 for(i1=1;i1<=4;i1++) 85 a[i1]=cur.s[i1]; 86 a[j]=(endx-1)*8+endy; 87 qsort(a+1,4,sizeof(a[1]),cmp1); 88 if(visit1[a[1]][a[2]][a[3]][a[4]]) continue; 89 if(visit2[a[1]][a[2]][a[3]][a[4]]) return 1; 90 visit1[a[1]][a[2]][a[3]][a[4]]=1; 91 next.step=cur.step+1; 92 for(i1=1;i1<=4;i1++) 93 next.s[i1]=a[i1]; 94 q1.push(next); 95 } 96 } 97 } 98 } 99 100 while(1) 101 { 102 cur=q2.front(); 103 q2.pop(); 104 if(cur.step>ncase) {q2.push(cur);break;} 105 if(cur.step==4) return 0; 106 for(i=0;i<4;i++) 107 { 108 for(j=1;j<=4;j++) 109 { 110 ansx=(cur.s[j]+7)/8; 111 ansy=cur.s[j]-(ansx-1)*8; 112 endx=ansx+dir[i][0]; 113 endy=ansy+dir[i][1]; 114 if(endx<=0 || endx>8||endy<=0 || endy>8) continue; 115 for(k=1;k<=4;k++) 116 if((endx-1)*8+endy == cur.s[k]) break; ///相邻的位置是否已占 117 if(k==5) 118 { 119 for(i1=1;i1<=4;i1++) 120 a[i1]=cur.s[i1]; 121 a[j]=(endx-1)*8+endy; 122 qsort(a+1,4,sizeof(a[1]),cmp1); 123 if(!visit2[a[1]][a[2]][a[3]][a[4]]) 124 { 125 if(visit1[a[1]][a[2]][a[3]][a[4]]) return 1; 126 visit2[a[1]][a[2]][a[3]][a[4]]=1; 127 next.step=cur.step+1; 128 for(i1=1;i1<=4;i1++) 129 next.s[i1]=a[i1]; 130 q2.push(next); 131 } 132 } 133 else 134 { 135 endx+=dir[i][0]; 136 endy+=dir[i][1]; 137 if(endx<=0 || endx>8 || endy<=0 || endy>8) continue; 138 for(i1=1;i1<=4;i1++) 139 if((endx-1)*8+endy==cur.s[i1]) break; 140 if(i1<=4) continue;//能否跳一个格 141 for(i1=1;i1<=4;i1++) 142 a[i1]=cur.s[i1]; 143 a[j]=(endx-1)*8+endy; 144 qsort(a+1,4,sizeof(a[1]),cmp1); 145 if(visit2[a[1]][a[2]][a[3]][a[4]]) continue; 146 if(visit1[a[1]][a[2]][a[3]][a[4]]) return 1; 147 visit2[a[1]][a[2]][a[3]][a[4]]=1; 148 next.step=cur.step+1; 149 for(i1=1;i1<=4;i1++) 150 next.s[i1]=a[i1]; 151 q2.push(next); 152 } 153 } 154 } 155 } 156 157 } 158 return 0; 159 } 160 int main() 161 { 162 int i,x,y; 163 while(scanf("%d",&x)!=EOF) 164 { 165 scanf("%d",&y); 166 st[1]=(x-1)*8+y; 167 for(i=2;i<=4;i++) 168 { 169 scanf("%d%d",&x,&y); 170 st[i]=(x-1)*8+y; 171 } 172 qsort(st+1,4,sizeof(st[1]),cmp1); 173 for(i=1;i<=4;i++) 174 { 175 scanf("%d%d",&x,&y); 176 end[i]=(x-1)*8+y; 177 } 178 qsort(end+1,4,sizeof(end[1]),cmp1); 179 memset(visit1,0,sizeof(visit1)); 180 memset(visit2,0,sizeof(visit2)); 181 if(bfs()) printf("YES\n"); 182 else printf("NO\n"); 183 } 184 return 0; 185 }