HDOJ 2428 Stars

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

成都网络赛第一题，比赛中是Teddy和 WYB一起A掉了。
比赛中觉得对这题挺有想法，现在拿回来做WA了20次……不过好歹是过掉了，离散化用的不多是主要原因，层出不穷的小错误也让我改到崩溃，看来我今天脑子被撞坏了。
我的做法是，先把出现的坐标值全部插入到数组中，排序后离散化，并替代原来的点的坐标，用hash标记，但是这儿有一个要注意的地方(就是我WA这么多次的原因)，原来的值一定不能丢掉，这在后面差值的比较中会用到。接着按坐标轴上从上往下，从左到右的顺序排序，然后枚举不同的两个点，看是否能够作为一个正方形的对角线，如果可以，那么看看另外两个点有没有被hash过……
贴下代码:

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. struct node{
  5.     int i;
  6.     int j;
  7. };
  8. node d[1011];
  9. int n;
  10. int ls[2012];
  11. int tt[20100];
  12. int hash[2011][2011];
  13.  
  14. inline bool cmp(node x, node y)
  15. {
  16.     if(x.i == y.i)
  17.         return x.j < y.j;
  18.     else
  19.         return x.i > y.i;
  20. }
  21.  
  22. int main()
  23. {
  24.     int t, i, j, k, ret, cas = 0;
  25.     scanf("%d", &t);
  26.     while(t--)
  27.     {
  28.         scanf("%d", &n);
  29.         cas ++;
  30.         if(n < 4) {
  31.             for(i = 0; i < n; i++)
  32.                 scanf("%d %d", &d[i].j, &d[i].i);
  33.             printf("0n");
  34.             continue;
  35.         }
  36.         j = 0;
  37.         for(i = 0; i < n; i++)
  38.         {
  39.             scanf("%d %d", &d[i].j, &d[i].i);
  40.             ls[j++] = d[i].i;
  41.             ls[j++] = d[i].j;
  42.         }
  43.         sort(ls, ls + j);
  44.         k = 0;
  45.         memset(tt, -1, sizeof(tt));
  46.         for(i = 0; i < j; i++)
  47.         {
  48.             if(tt[ls[i] + 10000] >= 0)
  49.                 continue;
  50.             else
  51.             {
  52.                 tt[ls[i] + 10000] = k;
  53.                 ls[k] = ls[i];
  54.                 k++;
  55.             }
  56.         }
  57.         for(i = 0; i < n; i++)
  58.         {
  59.             d[i].i = tt[d[i].i + 10000];
  60.             d[i].j = tt[d[i].j + 10000];
  61.             hash[d[i].i][d[i].j] = cas;
  62.         }
  63.         sort(d, d+n, cmp);
  64.         ret = 0;
  65.         for(i = 0; i < n; i++)
  66.             for(j = i + 1; j < n; j++)
  67.             {
  68.                 if(d[i].i == d[j].i || d[i].j >= d[j].j)
  69.                     continue;
  70.                 if((ls[d[i].i] - ls[d[j].i]) != (ls[d[j].j] - ls[d[i].j]))
  71.                     continue;
  72.                 if(hash[d[i].i][d[j].j] == cas && hash[d[j].i][d[i].j] == cas)
  73.                     ret++;
  74.             }
  75.         printf("%dn", ret);
  76.     }
  77.     return 0;
  78. }

,

No Comments

一个段落

Posted by twcai in My Life on October 21, 2008

终于，排在周末的比赛都告一段落了，但是regional还有一个月多的时间才结束……好歹现在周末也有机会空出一天去看书了.
时间不多，我还是很弱，现在把暑假的那些落下的专题都捡回来做了，不做真的不行。
换了个主题，其实原来那些主题都很优秀，不过不符合我的习惯（IDE看久了总是希望能在一个页面内看到尽量多的内容）所以老是去涂涂改改，现在理解了那些作者设计的理念，就是是为了照顾有不同习惯的人和有视力障碍的阅读者，于是就没有一定要去改变原来的模板的执念了。
YouTube上看到Jay的 “说好的幸福呢” 的MV，那个女主角真的很赞，歌也听了很多遍，分享下
去收集女主角的可爱PP了^^

, ,

No Comments

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