HDOJ 1732 Push Box

Posted by twcai in ACM/ICPC on October 18, 2008

推箱子，一共有三个箱子，没想出什么特别的方法，就直接用了盲目广搜了。写了很久-_-除了大数模板外我写的最长的一道题目了吧，刚开始RE，hash的时候没处理好，再检查了一下小错误，居然就过掉了……我还以为这道题起码还要搞掉我两天，RP还行。
我是用坐标来储存结点状态，一共6个坐标，每个3位，不过箱子的实际状态比这个要小很多，因为箱子所在的点是不能重复的，大概5000的数组就够用了。
中间还加了个剪枝，就是剪掉有某个点旁边已经有相邻两处被堵死的情况，这个剪枝优化还是比较明显的。
贴下代码：

  1. #include <iostream>
  2. using namespace std;
  3. #define MAX 500000
  4. #define HF 5555
  5.  
  6. int dir[4][2]={{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
  7. int END, n, m;
  8. char ma[8][10];
  9. int hash[8][8][HF];
  10.  
  11. struct box{
  12.     int i;
  13.     int j;
  14. };
  15. box bo[3], ho[3];
  16.  
  17. struct node{
  18.     int ni;
  19.     int nj;
  20.     int t;
  21.     int sta;
  22. };
  23. node now, next;
  24. node qq[MAX];
  25.  
  26. inline bool valid(const node &x)
  27. {
  28.     return (x.ni>=0 && x.nj>= 0 && x.ni<n && x.nj<m);
  29. }
  30.  
  31. inline bool valid(const box &x)
  32. {
  33.     return (x.i>=0 && x.j>=0 && x.i<n && x.j<m);
  34. }
  35.  
  36. inline bool cmp(const box &x,const box &y)
  37. {
  38.     if(x.i == y.i)
  39.         return x.j < y.j;
  40.     else return x.i < y.i;
  41. }
  42.  
  43. inline void st(box x[])
  44. {
  45.     box tmp;
  46.     if(!cmp(x[0], x[1]))
  47.     {
  48.         tmp = x[0];
  49.         x[0] = x[1];
  50.         x[1] = tmp;
  51.     }
  52.     if(!cmp(x[0], x[2]))
  53.     {
  54.         tmp = x[0];
  55.         x[0] = x[2];
  56.         x[2] = tmp;
  57.     }
  58.     if(!cmp(x[1], x[2]))
  59.     {
  60.         tmp = x[1];
  61.         x[1] = x[2];
  62.         x[2] = tmp;
  63.     }
  64. }
  65.  
  66. void init()
  67. {
  68.     int i;
  69.     now.sta = 0;
  70.     now .t = 0;
  71.     for(i = 0; i < 3; i++)
  72.     {
  73.         now.sta <<= 3;
  74.         now.sta += bo[i].i;
  75.         now.sta <<= 3;
  76.         now.sta += bo[i].j;
  77.     }
  78.     st(ho); END = 0;
  79.     for(i = 0; i < 3; i++)
  80.     {
  81.         END <<= 3;
  82.         END += ho[i].i;
  83.         END <<= 3;
  84.         END += ho[i].j;
  85.     }
  86. }
  87.  
  88. inline bool dead(int x)
  89. {
  90.     int i, j, k;
  91.     bool c[4];
  92.     box tmp;
  93.     for(i = 0; i < 3; i++)
  94.     {
  95.         bo[i].j = x%8;
  96.         x >>= 3;
  97.         bo[i].i = x%8;
  98.         x >>= 3;
  99.     }
  100.     for(i = 0; i < 3; i++)
  101.     {
  102.         if(ma[bo[i].i][bo[i].j] == '@') continue;
  103.         for(k = 0; k < 4; k++)
  104.             c[k] = 0;
  105.         for(j = 0; j < 4; j++)
  106.         {
  107.             tmp.i = bo[i].i + dir[j][0];
  108.             tmp.j = bo[i].j + dir[j][1];
  109.             if(!valid(tmp))
  110.                 c[j] = 1;
  111.             else if(ma[tmp.i][tmp.j] == '#')
  112.                 c[j] = 1;
  113.             else {
  114.                 for(k = 0; k < 3; k++)
  115.                 {
  116.                     if(k == i) continue;
  117.                     if((bo[i].i == bo[k].i) && (bo[i].j == bo[k].j))
  118.                     {
  119.                         c[j] = 1;
  120.                         break;
  121.                     }
  122.                 }
  123.             }
  124.         }
  125.         for(j = 0; j < 4; j++)
  126.             if(c[j] == 1)
  127.             {
  128.                 k = j + 1;
  129.                 if(k == 4) k=0;
  130.                 if(c[k] == 1)
  131.                     return true;
  132.             }
  133.     }
  134.     return false;
  135. }
  136.  
  137. inline int bfs()
  138. {
  139.     int flag, vfun;
  140.     box tmp;
  141.     int low = 0, high = 0, i, j;
  142.     memset(hash, -1, sizeof(hash));
  143.     qq[high++] = now;
  144.     hash[now.ni][now.nj][now.sta % HF] = now.sta;
  145.  
  146.     while(low < high)
  147.     {
  148.         now = qq[low++];
  149.         if(now.sta == END) return now.t;
  150.         if(low >= MAX) low %= MAX;
  151.         for(i = 0; i < 4; i++)
  152.         {
  153.             next.ni = now.ni + dir[i][0];
  154.             next.nj = now.nj + dir[i][1];
  155.             if(dead(now.sta)) continue;
  156.             if(!valid(next) || ma[next.ni][next.nj] == '#') continue;
  157.             next.sta = now.sta;
  158.             flag = -1;
  159.             for(j = 0; j < 3 && flag == -1; j++)
  160.             {
  161.                 bo[j].j = next.sta % 8;
  162.                 next.sta >>= 3;
  163.                 bo[j].i = next.sta % 8;
  164.                 next.sta >>= 3;
  165.                 if(bo[j].i == next.ni && bo[j].j == next.nj)
  166.                     flag = j;
  167.             }
  168.             if(flag == -1)
  169.             {
  170.                 next.sta = now.sta;
  171.                 vfun = next.sta % HF;
  172.                 while(hash[next.ni][next.nj][vfun] != -1 && hash[next.ni][next.nj][vfun] != next.sta)
  173.                 {
  174.                     vfun+=7;
  175.                     if(vfun >= HF) vfun %= HF;
  176.                 }
  177.                 if(hash[next.ni][next.nj][vfun] == next.sta) continue;
  178.                 else
  179.                     hash[next.ni][next.nj][vfun] = next.sta;
  180.                 next.t = now .t + 1;
  181.                 qq[high++] = next;
  182.                 if(high >= MAX) high %= MAX;
  183.             }
  184.             else {
  185.                 tmp.i = next.ni + dir[i][0];
  186.                 tmp.j = next.nj + dir[i][1];
  187.                 if(!valid(tmp) || ma[tmp.i][tmp.j] == '#') continue;
  188.                 for(j = 0; j < 3; j++)
  189.                 {
  190.                     if(flag == j) continue;
  191.                     if(tmp.i == bo[j].i && tmp.j == bo[j].j)
  192.                     {
  193.                         flag = -1; break;
  194.                     }
  195.                 }
  196.                 if(flag == -1) continue;
  197.                 else {
  198.                     bo[flag].i = tmp.i;
  199.                     bo[flag].j = tmp.j;
  200.                     st(bo);
  201.                     next.sta = 0;
  202.                     for(j = 0; j < 3; j++)
  203.                     {
  204.                         next.sta <<= 3;
  205.                         next.sta += bo[j].i;
  206.                         next.sta <<= 3;
  207.                         next.sta += bo[j].j;
  208.                     }
  209.                     vfun = next.sta % HF;
  210.                     while(hash[next.ni][next.nj][vfun] != -1 && hash[next.ni][next.nj][vfun] != next.sta)
  211.                     {
  212.                         vfun+=7;
  213.                         if(vfun >= HF) vfun %=HF;
  214.                     }
  215.                     if(hash[next.ni][next.nj][vfun] == next.sta) continue;
  216.                     else {
  217.                         hash[next.ni][next.nj][vfun] = next.sta;
  218.                     }
  219.                     next.t = now.t + 1;
  220.                     qq[high++] = next;
  221.                     if(high >= MAX) high %= MAX;
  222.                 }
  223.             }
  224.         }
  225.     }
  226.     return -1;
  227. }
  228.  
  229. int main()
  230. {
  231.     int i, j;
  232.     int cb, ch, ret;
  233.  
  234.     while(scanf("%d %d", &n, &m)!= EOF)
  235.     {
  236.         getchar();
  237.         cb = 0; ch = 0;
  238.         for(i = 0; i < n; i++)
  239.         {
  240.             gets(ma[i]);
  241.             for(j = 0; j < m; j++)
  242.             {
  243.                 if(ma[i][j] == '@')
  244.                 {
  245.                     ho[ch].i = i;
  246.                     ho[ch++].j = j;
  247.                 }
  248.                 else if(ma[i][j] == '*')
  249.                 {
  250.                     bo[cb].i = i;
  251.                     bo[cb++].j = j;
  252.                     ma[i][j] = '.';
  253.                 }
  254.                 else if(ma[i][j] == 'X')
  255.                 {
  256.                     now.ni = i;
  257.                     now.nj = j;
  258.                     ma[i][j] = '.';
  259.                 }
  260.             }
  261.         }
  262.         init();
  263.         ret = bfs();
  264.         printf("%dn", ret);
  265.     }
  266.     return 0;
  267. }

,

No Comments

HDOJ 1401

Posted by twcai in ACM/ICPC on October 6, 2008

Solitaire,比较单纯的双广,考虑了下怎么保存棋子的状态,然后直接开搜. MS别人都是用两个queue来做的……
第一次写双广,效率不是很高。
一共有四个棋子，一个坐标需要3位来存，这是数是蛮大的，但实际状态64万就够用了，普通的hash能够搞定。
贴下代码：

  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. #define MAX 235536
  5.  
  6. int h[MAX];
  7. int v[MAX];
  8. int dir[4][2]={0,1,-1,0,0,-1,1,0};
  9.  
  10. struct chess{
  11.     int i;
  12.     int j;
  13. };
  14.  
  15. struct pos{
  16.     chess c[4];
  17.     int sta;
  18.     int t;
  19.     int fl;
  20. };
  21. queue <pos> ch;
  22. pos s,e,now,next;
  23.  
  24. inline bool cmp(const chess x,const chess y)
  25. {
  26.     if(x.i==y.i) return x.j<y.j;
  27.     else return x.i<y.i;
  28. }
  29.  
  30. inline bool valid(chess x)
  31. {
  32.     return (x.i>=0 && x.j>=0 && x.i<8 && x.j<8);
  33. }
  34.  
  35. inline int encode(pos x)
  36. {
  37.     int i;
  38.     int sta=0;
  39.     sort(x.c, x.c+4, cmp);
  40.     for(i=0;i<4;i++)
  41.     {
  42.         sta<<=3;
  43.         sta+=x.c[i].i;
  44.         sta<<=3;
  45.         sta+=x.c[i].j;
  46.     }
  47.     return sta;
  48. }
  49.  
  50. inline bool bfs()
  51. {
  52.     int i,j,k,t,l;
  53.     bool flag;
  54.  
  55.     memset(h,-1,sizeof(h));
  56.     memset(v,-1,sizeof(v));
  57.     while(!ch.empty()) ch.pop();
  58.  
  59.     s.t=0; s.fl=1;
  60.     s.sta=encode(s);
  61.     e.t=0; e.fl=2;
  62.     e.sta=encode(e);
  63.     if(s.sta == e.sta) return true;
  64.  
  65.     t=s.sta%MAX;
  66.     while(h[t]!=-1 && v[t]!=s.sta){
  67.         t+=10;
  68.         if(t>=MAX) t%=MAX;
  69.     }
  70.     h[t]=s.fl; v[t]=s.sta;
  71.     t=e.sta%MAX;
  72.     while(h[t]!=-1 && v[t]!=s.sta){
  73.         t+=10;
  74.         if(t>=MAX) t%=MAX;
  75.     }
  76.     h[t]=e.fl; v[t]=e.sta;
  77.     ch.push(s); ch.push(e);
  78.  
  79.     while(!ch.empty()){
  80.         now=ch.front(); ch.pop();
  81.         if(now.t>3) continue;
  82.         for(i=0;i<4;i++){
  83.             for (j=0;j<4;j++){
  84.                 next.c[j].i=now.c[j].i;
  85.                 next.c[j].j=now.c[j].j;
  86.             }
  87.             for(j=0;j<4;j++){
  88.                 if(j){
  89.                     next.c[j-1].i=now.c[j-1].i;
  90.                     next.c[j-1].j=now.c[j-1].j;
  91.                 }
  92.                 next.c[j].i+=dir[i][0];
  93.                 next.c[j].j+=dir[i][1];
  94.                 if(!valid(next.c[j])) continue;
  95.                 flag=0;
  96.                 for(k=0;k<4 && !flag;k++){
  97.                     if(j==k) continue;
  98.                     if(next.c[j].i==next.c[k].i && next.c[j].j==next.c[k].j)
  99.                         flag=1;
  100.                 }
  101.                 if(!flag){
  102.                     next.sta=encode(next);
  103.                     next.fl=now.fl;
  104.                     t=next.sta%MAX;
  105.                     while(h[t]!=-1 && v[t]!=next.sta){
  106.                         t+=10;
  107.                         if(t>=MAX) t%=MAX;
  108.                     }
  109.                     if(v[t]==next.sta) {
  110.                         if(h[t]!=next.fl) return true;
  111.                         else continue;
  112.                     }
  113.                     else {
  114.                         next.t=now.t+1;
  115.                         if(next.t>4) continue;
  116.                         h[t]=next.fl;
  117.                         v[t]=next.sta;
  118.                         ch.push(next);
  119.                     }
  120.                 }
  121.                 else {
  122.                     next.c[j].i+=dir[i][0];
  123.                     next.c[j].j+=dir[i][1];
  124.                     if(!valid(next.c[j])) continue;
  125.                     flag=0;
  126.                     for(k=0;k<4 && !flag;k++){
  127.                         if(j==k) continue;
  128.                         if(next.c[j].i==next.c[k].i && next.c[j].j==next.c[k].j)
  129.                             flag=1;
  130.                     }
  131.                     if(flag) continue;
  132.                     else {
  133.                         next.fl=now.fl;
  134.                         next.sta=encode(next);
  135.                         t=next.sta%MAX;
  136.                         while(h[t]!=-1 && v[t]!=next.sta){
  137.                             t+=10;
  138.                             if(t>=MAX) t%=MAX;
  139.                         }
  140.                         if(v[t]==next.sta) {
  141.                             if(h[t]!=next.fl) return true;
  142.                             else continue;
  143.                         }
  144.                         else {
  145.                             next.t=now.t+1;
  146.                             if(next.t>4) continue;
  147.                             h[t]=next.fl;
  148.                             v[t]=next.sta;
  149.                             ch.push(next);
  150.                         }
  151.                     }
  152.                 }
  153.             }
  154.         }
  155.     }
  156.     return false;
  157. }
  158.  
  159. int main()
  160. {
  161.     int i;
  162.     bool ret;
  163.  
  164.     while(scanf("%d",&s.c[0].i)!=EOF){
  165.         scanf("%d",&s.c[0].j);
  166.         for(i=1;i<4;i++)
  167.             scanf("%d %d",&s.c[i].i,&s.c[i].j);
  168.         for(i=0;i<4;i++)
  169.             scanf("%d %d",&e.c[i].i,&e.c[i].j);
  170.         for(i=0;i<4;i++)
  171.         {
  172.             s.c[i].i--;s.c[i].j--;
  173.             e.c[i].i--;e.c[i].j--;
  174.         }
  175.  
  176.         ret=bfs();
  177.         if(ret) printf("YESn");
  178.         else printf("NOn");
  179.     }
  180.     return 0;
  181. }

,

2 Comments

HDOJ 1180

Posted by twcai in ACM/ICPC on October 3, 2008

诡异的楼梯，一道蛮单纯的广搜题，不过我觉得有些细节还是比较值得注意的(我忽略了过楼梯后的若干情况)。
相对其他换汤不换药的迷宫来说，蛮有意思。

  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. char ma[22][22];
  6. int hash[22][22];
  7. int dir[4][2]={0,1,-1,0,0,-1,1,0};
  8. int n,m;
  9. struct node{
  10.     int ni;
  11.     int nj;
  12.     int t;
  13. };
  14. node now,next;
  15. priority_queue <node> hp;
  16.  
  17. inline bool operator<(const node &x,const node &y)
  18. {
  19.     return x.t>y.t;
  20. }
  21.  
  22. inline bool valid(const node &x)
  23. {
  24.     return (x.ni>=0 && x.nj>=0 && x.ni<n && x.nj<m);
  25. }
  26.  
  27. inline int bfs()
  28. {
  29.     int i;
  30.     int sd;
  31.     while(!hp.empty()) hp.pop();
  32.     memset(hash,0,sizeof(hash));
  33.     hash[now.ni][now.nj]=1;
  34.     hp.push(now);
  35.     while(!hp.empty())
  36.     {
  37.         now=hp.top();hp.pop();
  38.         if(ma[now.ni][now.nj]=='T')
  39.             return now.t;
  40.         for(i=0;i<4;i++)
  41.         {
  42.             next.ni=now.ni+dir[i][0];
  43.             next.nj=now.nj+dir[i][1];
  44.             if(!valid(next) || ma[next.ni][next.nj]=='*') continue;
  45.             if(hash[next.ni][next.nj]) continue;
  46.             if(ma[next.ni][next.nj]=='T' || ma[next.ni][next.nj]=='.')
  47.             {
  48.                 next.t=now.t+1;
  49.                 hp.push(next);
  50.                 hash[next.ni][next.nj]=1;
  51.                 continue;
  52.             }
  53.  
  54.             if(ma[next.ni][next.nj]=='-' && (i&1)==0)
  55.                 sd=1;
  56.             else if(ma[next.ni][next.nj]=='|' && (i&1)==1)
  57.                 sd=1;
  58.             else sd=0;
  59.             next.ni+=dir[i][0];
  60.             next.nj+=dir[i][1];
  61.             if(!valid(next) || ma[next.ni][next.nj]=='*') continue;
  62.             if(hash[next.ni][next.nj]) continue;
  63.             if(((now.t&1)==0 && sd==1) || ((now.t&1)==1 && sd==0))
  64.                 next.t=now.t+1;
  65.             else
  66.                 next.t=now.t+2;
  67.             hash[next.ni][next.nj]=1;
  68.             hp.push(next);
  69.         }
  70.     }
  71.     return 0;
  72. }
  73.  
  74. int main()
  75. {
  76.     bool flag;
  77.     int i,j,ret;
  78.     while(scanf("%d %d",&n,&m)!=EOF)
  79.     {
  80.         getchar(); flag=0;
  81.         for(i=0;i<n;i++)
  82.         {
  83.             gets(ma[i]);
  84.             for(j=0;j<m && !flag;j++)
  85.                 if(ma[i][j]=='S'){
  86.                     now.ni=i;
  87.                     now.nj=j;
  88.                     now.t=0;
  89.                     flag=1;
  90.                 }
  91.         }
  92.         ret=bfs();
  93.         printf("%dn",ret);
  94.     }
  95.     return 0;
  96. }

No Comments

我真搓

Posted by twcai in My Life on September 30, 2008

这两场比赛都很郁闷，感觉像梦游，而且都是刚好在这两场加权的网络赛上。- -!
其他队员经过一个暑假集训都成长了好多，但我却好像根本没什么进步，现在也许我是整个集训队最弱的队员吧。记得暑假刚开始，lcy老师曾经在论坛里发贴跟我说：高手都是要以题量为保证的，指出我做题的数量太少。那时候我也听进去了，但心里总还有一点觉得我被刘老师给bs了。今天想想，觉得其实完全不是那样的，正是因为对我抱有期望所以才来指出我的短处啊。唉～～暑假都结束一个月了，可以看看我的这三个月来，只做了那么点题目，专题的跟进更是不行，跟托蒂简直不能比，太可怜啦。。
自从被szm指责后，我已经改掉了老喜欢发表决心的毛病了。但我觉得这次真的有必要下一次决心，要把以前落下的都一样一样补上！

No Comments

08-9-27

Posted by twcai in My Life on September 27, 2008

非常舒服的天气，也许是lcd盯太久了，偶尔抬头看天，就会有一种刺眼+震撼的感觉。那种湛蓝的颜色以及从视线边际射过来的光线让我不得不眯着眼睛，但是又充斥着就这么一直看下去的欲望。
是不是说明我真的变成一个宅男啦。
不知道为什么，如果被室外的风吹到有点凉意的时候，就会不由自主回忆起很多小时候的事情。且第一个闪过的画面总是自己趴在窗户边羡慕那些在楼下嬉戏的小孩，因为那时的我就很懒，总是不爱做作业所以老被老妈关在家里；那时候从窗外冲进来的风印象中就是这么带着点低温的伤感的。而后就是想起小学时老爸老妈常常带着我出去郊游的情景，低年级的我还是很乖的，每次都很快的把作文以外作业完成，然后星期天就可以出去郊游啦，我总是手里拿着一份树枝在行人踏出的小路上跑来跑去，并且去抽那些路边的野草。因为郊游大部分都在春天和秋天出去，地点也都在山上或者水边，那时候的风也是凉飕飕的。那时候应该还留下了蛮多照片的，不过我从高中后好像就没有去看过了，也许老爸老妈还偶尔会翻一下吧。
长大到底是好还是坏，很难说啊……

No Comments