HDOJ 2428 Stars
成都网络赛第一题,比赛中是Teddy和 WYB一起A掉了。
比赛中觉得对这题挺有想法,现在拿回来做WA了20次……不过好歹是过掉了,离散化用的不多是主要原因,层出不穷的小错误也让我改到崩溃,看来我今天脑子被撞坏了。
我的做法是,先把出现的坐标值全部插入到数组中,排序后离散化,并替代原来的点的坐标,用hash标记,但是这儿有一个要注意的地方(就是我WA这么多次的原因),原来的值一定不能丢掉,这在后面差值的比较中会用到。接着按坐标轴上从上往下,从左到右的顺序排序,然后枚举不同的两个点,看是否能够作为一个正方形的对角线,如果可以,那么看看另外两个点有没有被hash过……
贴下代码:
- #include <iostream>
- #include <algorithm>
- using namespace std;
- struct node{
- int i;
- int j;
- };
- node d[1011];
- int n;
- int ls[2012];
- int tt[20100];
- int hash[2011][2011];
- inline bool cmp(node x, node y)
- {
- if(x.i == y.i)
- return x.j < y.j;
- else
- return x.i > y.i;
- }
- int main()
- {
- int t, i, j, k, ret, cas = 0;
- scanf("%d", &t);
- while(t--)
- {
- scanf("%d", &n);
- cas ++;
- if(n < 4) {
- for(i = 0; i < n; i++)
- scanf("%d %d", &d[i].j, &d[i].i);
- printf("0n");
- continue;
- }
- j = 0;
- for(i = 0; i < n; i++)
- {
- scanf("%d %d", &d[i].j, &d[i].i);
- ls[j++] = d[i].i;
- ls[j++] = d[i].j;
- }
- sort(ls, ls + j);
- k = 0;
- memset(tt, -1, sizeof(tt));
- for(i = 0; i < j; i++)
- {
- if(tt[ls[i] + 10000] >= 0)
- continue;
- else
- {
- tt[ls[i] + 10000] = k;
- ls[k] = ls[i];
- k++;
- }
- }
- for(i = 0; i < n; i++)
- {
- d[i].i = tt[d[i].i + 10000];
- d[i].j = tt[d[i].j + 10000];
- hash[d[i].i][d[i].j] = cas;
- }
- sort(d, d+n, cmp);
- ret = 0;
- for(i = 0; i < n; i++)
- for(j = i + 1; j < n; j++)
- {
- if(d[i].i == d[j].i || d[i].j >= d[j].j)
- continue;
- if((ls[d[i].i] - ls[d[j].i]) != (ls[d[j].j] - ls[d[i].j]))
- continue;
- if(hash[d[i].i][d[j].j] == cas && hash[d[j].i][d[i].j] == cas)
- ret++;
- }
- printf("%dn", ret);
- }
- return 0;
- }
一个段落
终于,排在周末的比赛都告一段落了,但是regional还有一个月多的时间才结束……好歹现在周末也有机会空出一天去看书了.
时间不多,我还是很弱,现在把暑假的那些落下的专题都捡回来做了,不做真的不行。
换了个主题,其实原来那些主题都很优秀,不过不符合我的习惯(IDE看久了总是希望能在一个页面内看到尽量多的内容)所以老是去涂涂改改,现在理解了那些作者设计的理念,就是是为了照顾有不同习惯的人和有视力障碍的阅读者,于是就没有一定要去改变原来的模板的执念了。
YouTube上看到Jay的 “说好的幸福呢” 的MV,那个女主角真的很赞,歌也听了很多遍,分享下
去收集女主角的可爱PP了^^
HDOJ 1732 Push Box
推箱子,一共有三个箱子,没想出什么特别的方法,就直接用了盲目广搜了。写了很久-_-除了大数模板外我写的最长的一道题目了吧,刚开始RE,hash的时候没处理好,再检查了一下小错误,居然就过掉了……我还以为这道题起码还要搞掉我两天,RP还行。
我是用坐标来储存结点状态,一共6个坐标,每个3位,不过箱子的实际状态比这个要小很多,因为箱子所在的点是不能重复的,大概5000的数组就够用了。
中间还加了个剪枝,就是剪掉有某个点旁边已经有相邻两处被堵死的情况,这个剪枝优化还是比较明显的。
贴下代码:
- #include <iostream>
- using namespace std;
- #define MAX 500000
- #define HF 5555
- int dir[4][2]={{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
- int END, n, m;
- char ma[8][10];
- int hash[8][8][HF];
- struct box{
- int i;
- int j;
- };
- box bo[3], ho[3];
- struct node{
- int ni;
- int nj;
- int t;
- int sta;
- };
- node now, next;
- node qq[MAX];
- inline bool valid(const node &x)
- {
- return (x.ni>=0 && x.nj>= 0 && x.ni<n && x.nj<m);
- }
- inline bool valid(const box &x)
- {
- return (x.i>=0 && x.j>=0 && x.i<n && x.j<m);
- }
- inline bool cmp(const box &x,const box &y)
- {
- if(x.i == y.i)
- return x.j < y.j;
- else return x.i < y.i;
- }
- inline void st(box x[])
- {
- box tmp;
- if(!cmp(x[0], x[1]))
- {
- tmp = x[0];
- x[0] = x[1];
- x[1] = tmp;
- }
- if(!cmp(x[0], x[2]))
- {
- tmp = x[0];
- x[0] = x[2];
- x[2] = tmp;
- }
- if(!cmp(x[1], x[2]))
- {
- tmp = x[1];
- x[1] = x[2];
- x[2] = tmp;
- }
- }
- void init()
- {
- int i;
- now.sta = 0;
- now .t = 0;
- for(i = 0; i < 3; i++)
- {
- now.sta <<= 3;
- now.sta += bo[i].i;
- now.sta <<= 3;
- now.sta += bo[i].j;
- }
- st(ho); END = 0;
- for(i = 0; i < 3; i++)
- {
- END <<= 3;
- END += ho[i].i;
- END <<= 3;
- END += ho[i].j;
- }
- }
- inline bool dead(int x)
- {
- int i, j, k;
- bool c[4];
- box tmp;
- for(i = 0; i < 3; i++)
- {
- bo[i].j = x%8;
- x >>= 3;
- bo[i].i = x%8;
- x >>= 3;
- }
- for(i = 0; i < 3; i++)
- {
- if(ma[bo[i].i][bo[i].j] == '@') continue;
- for(k = 0; k < 4; k++)
- c[k] = 0;
- for(j = 0; j < 4; j++)
- {
- tmp.i = bo[i].i + dir[j][0];
- tmp.j = bo[i].j + dir[j][1];
- if(!valid(tmp))
- c[j] = 1;
- else if(ma[tmp.i][tmp.j] == '#')
- c[j] = 1;
- else {
- for(k = 0; k < 3; k++)
- {
- if(k == i) continue;
- if((bo[i].i == bo[k].i) && (bo[i].j == bo[k].j))
- {
- c[j] = 1;
- break;
- }
- }
- }
- }
- for(j = 0; j < 4; j++)
- if(c[j] == 1)
- {
- k = j + 1;
- if(k == 4) k=0;
- if(c[k] == 1)
- return true;
- }
- }
- return false;
- }
- inline int bfs()
- {
- int flag, vfun;
- box tmp;
- int low = 0, high = 0, i, j;
- memset(hash, -1, sizeof(hash));
- qq[high++] = now;
- hash[now.ni][now.nj][now.sta % HF] = now.sta;
- while(low < high)
- {
- now = qq[low++];
- if(now.sta == END) return now.t;
- if(low >= MAX) low %= MAX;
- for(i = 0; i < 4; i++)
- {
- next.ni = now.ni + dir[i][0];
- next.nj = now.nj + dir[i][1];
- if(dead(now.sta)) continue;
- if(!valid(next) || ma[next.ni][next.nj] == '#') continue;
- next.sta = now.sta;
- flag = -1;
- for(j = 0; j < 3 && flag == -1; j++)
- {
- bo[j].j = next.sta % 8;
- next.sta >>= 3;
- bo[j].i = next.sta % 8;
- next.sta >>= 3;
- if(bo[j].i == next.ni && bo[j].j == next.nj)
- flag = j;
- }
- if(flag == -1)
- {
- next.sta = now.sta;
- vfun = next.sta % HF;
- while(hash[next.ni][next.nj][vfun] != -1 && hash[next.ni][next.nj][vfun] != next.sta)
- {
- vfun+=7;
- if(vfun >= HF) vfun %= HF;
- }
- if(hash[next.ni][next.nj][vfun] == next.sta) continue;
- else
- hash[next.ni][next.nj][vfun] = next.sta;
- next.t = now .t + 1;
- qq[high++] = next;
- if(high >= MAX) high %= MAX;
- }
- else {
- tmp.i = next.ni + dir[i][0];
- tmp.j = next.nj + dir[i][1];
- if(!valid(tmp) || ma[tmp.i][tmp.j] == '#') continue;
- for(j = 0; j < 3; j++)
- {
- if(flag == j) continue;
- if(tmp.i == bo[j].i && tmp.j == bo[j].j)
- {
- flag = -1; break;
- }
- }
- if(flag == -1) continue;
- else {
- bo[flag].i = tmp.i;
- bo[flag].j = tmp.j;
- st(bo);
- next.sta = 0;
- for(j = 0; j < 3; j++)
- {
- next.sta <<= 3;
- next.sta += bo[j].i;
- next.sta <<= 3;
- next.sta += bo[j].j;
- }
- vfun = next.sta % HF;
- while(hash[next.ni][next.nj][vfun] != -1 && hash[next.ni][next.nj][vfun] != next.sta)
- {
- vfun+=7;
- if(vfun >= HF) vfun %=HF;
- }
- if(hash[next.ni][next.nj][vfun] == next.sta) continue;
- else {
- hash[next.ni][next.nj][vfun] = next.sta;
- }
- next.t = now.t + 1;
- qq[high++] = next;
- if(high >= MAX) high %= MAX;
- }
- }
- }
- }
- return -1;
- }
- int main()
- {
- int i, j;
- int cb, ch, ret;
- while(scanf("%d %d", &n, &m)!= EOF)
- {
- getchar();
- cb = 0; ch = 0;
- for(i = 0; i < n; i++)
- {
- gets(ma[i]);
- for(j = 0; j < m; j++)
- {
- if(ma[i][j] == '@')
- {
- ho[ch].i = i;
- ho[ch++].j = j;
- }
- else if(ma[i][j] == '*')
- {
- bo[cb].i = i;
- bo[cb++].j = j;
- ma[i][j] = '.';
- }
- else if(ma[i][j] == 'X')
- {
- now.ni = i;
- now.nj = j;
- ma[i][j] = '.';
- }
- }
- }
- init();
- ret = bfs();
- printf("%dn", ret);
- }
- return 0;
- }
HDOJ 1401
Solitaire,比较单纯的双广,考虑了下怎么保存棋子的状态,然后直接开搜. MS别人都是用两个queue来做的……
第一次写双广,效率不是很高。
一共有四个棋子,一个坐标需要3位来存,这是数是蛮大的,但实际状态64万就够用了,普通的hash能够搞定。
贴下代码:
- #include <iostream>
- #include <queue>
- using namespace std;
- #define MAX 235536
- int h[MAX];
- int v[MAX];
- int dir[4][2]={0,1,-1,0,0,-1,1,0};
- struct chess{
- int i;
- int j;
- };
- struct pos{
- chess c[4];
- int sta;
- int t;
- int fl;
- };
- queue <pos> ch;
- pos s,e,now,next;
- inline bool cmp(const chess x,const chess y)
- {
- if(x.i==y.i) return x.j<y.j;
- else return x.i<y.i;
- }
- inline bool valid(chess x)
- {
- return (x.i>=0 && x.j>=0 && x.i<8 && x.j<8);
- }
- inline int encode(pos x)
- {
- int i;
- int sta=0;
- sort(x.c, x.c+4, cmp);
- for(i=0;i<4;i++)
- {
- sta<<=3;
- sta+=x.c[i].i;
- sta<<=3;
- sta+=x.c[i].j;
- }
- return sta;
- }
- inline bool bfs()
- {
- int i,j,k,t,l;
- bool flag;
- memset(h,-1,sizeof(h));
- memset(v,-1,sizeof(v));
- while(!ch.empty()) ch.pop();
- s.t=0; s.fl=1;
- s.sta=encode(s);
- e.t=0; e.fl=2;
- e.sta=encode(e);
- if(s.sta == e.sta) return true;
- t=s.sta%MAX;
- while(h[t]!=-1 && v[t]!=s.sta){
- t+=10;
- if(t>=MAX) t%=MAX;
- }
- h[t]=s.fl; v[t]=s.sta;
- t=e.sta%MAX;
- while(h[t]!=-1 && v[t]!=s.sta){
- t+=10;
- if(t>=MAX) t%=MAX;
- }
- h[t]=e.fl; v[t]=e.sta;
- ch.push(s); ch.push(e);
- while(!ch.empty()){
- now=ch.front(); ch.pop();
- if(now.t>3) continue;
- for(i=0;i<4;i++){
- for (j=0;j<4;j++){
- next.c[j].i=now.c[j].i;
- next.c[j].j=now.c[j].j;
- }
- for(j=0;j<4;j++){
- if(j){
- next.c[j-1].i=now.c[j-1].i;
- next.c[j-1].j=now.c[j-1].j;
- }
- next.c[j].i+=dir[i][0];
- next.c[j].j+=dir[i][1];
- if(!valid(next.c[j])) continue;
- flag=0;
- for(k=0;k<4 && !flag;k++){
- if(j==k) continue;
- if(next.c[j].i==next.c[k].i && next.c[j].j==next.c[k].j)
- flag=1;
- }
- if(!flag){
- next.sta=encode(next);
- next.fl=now.fl;
- t=next.sta%MAX;
- while(h[t]!=-1 && v[t]!=next.sta){
- t+=10;
- if(t>=MAX) t%=MAX;
- }
- if(v[t]==next.sta) {
- if(h[t]!=next.fl) return true;
- else continue;
- }
- else {
- next.t=now.t+1;
- if(next.t>4) continue;
- h[t]=next.fl;
- v[t]=next.sta;
- ch.push(next);
- }
- }
- else {
- next.c[j].i+=dir[i][0];
- next.c[j].j+=dir[i][1];
- if(!valid(next.c[j])) continue;
- flag=0;
- for(k=0;k<4 && !flag;k++){
- if(j==k) continue;
- if(next.c[j].i==next.c[k].i && next.c[j].j==next.c[k].j)
- flag=1;
- }
- if(flag) continue;
- else {
- next.fl=now.fl;
- next.sta=encode(next);
- t=next.sta%MAX;
- while(h[t]!=-1 && v[t]!=next.sta){
- t+=10;
- if(t>=MAX) t%=MAX;
- }
- if(v[t]==next.sta) {
- if(h[t]!=next.fl) return true;
- else continue;
- }
- else {
- next.t=now.t+1;
- if(next.t>4) continue;
- h[t]=next.fl;
- v[t]=next.sta;
- ch.push(next);
- }
- }
- }
- }
- }
- }
- return false;
- }
- int main()
- {
- int i;
- bool ret;
- while(scanf("%d",&s.c[0].i)!=EOF){
- scanf("%d",&s.c[0].j);
- for(i=1;i<4;i++)
- scanf("%d %d",&s.c[i].i,&s.c[i].j);
- for(i=0;i<4;i++)
- scanf("%d %d",&e.c[i].i,&e.c[i].j);
- for(i=0;i<4;i++)
- {
- s.c[i].i--;s.c[i].j--;
- e.c[i].i--;e.c[i].j--;
- }
- ret=bfs();
- if(ret) printf("YESn");
- else printf("NOn");
- }
- return 0;
- }
HDOJ 1180
诡异的楼梯,一道蛮单纯的广搜题,不过我觉得有些细节还是比较值得注意的(我忽略了过楼梯后的若干情况)。
相对其他换汤不换药的迷宫来说,蛮有意思。
- #include <iostream>
- #include <queue>
- using namespace std;
- char ma[22][22];
- int hash[22][22];
- int dir[4][2]={0,1,-1,0,0,-1,1,0};
- int n,m;
- struct node{
- int ni;
- int nj;
- int t;
- };
- node now,next;
- priority_queue <node> hp;
- inline bool operator<(const node &x,const node &y)
- {
- return x.t>y.t;
- }
- inline bool valid(const node &x)
- {
- return (x.ni>=0 && x.nj>=0 && x.ni<n && x.nj<m);
- }
- inline int bfs()
- {
- int i;
- int sd;
- while(!hp.empty()) hp.pop();
- memset(hash,0,sizeof(hash));
- hash[now.ni][now.nj]=1;
- hp.push(now);
- while(!hp.empty())
- {
- now=hp.top();hp.pop();
- if(ma[now.ni][now.nj]=='T')
- return now.t;
- for(i=0;i<4;i++)
- {
- next.ni=now.ni+dir[i][0];
- next.nj=now.nj+dir[i][1];
- if(!valid(next) || ma[next.ni][next.nj]=='*') continue;
- if(hash[next.ni][next.nj]) continue;
- if(ma[next.ni][next.nj]=='T' || ma[next.ni][next.nj]=='.')
- {
- next.t=now.t+1;
- hp.push(next);
- hash[next.ni][next.nj]=1;
- continue;
- }
- if(ma[next.ni][next.nj]=='-' && (i&1)==0)
- sd=1;
- else if(ma[next.ni][next.nj]=='|' && (i&1)==1)
- sd=1;
- else sd=0;
- next.ni+=dir[i][0];
- next.nj+=dir[i][1];
- if(!valid(next) || ma[next.ni][next.nj]=='*') continue;
- if(hash[next.ni][next.nj]) continue;
- if(((now.t&1)==0 && sd==1) || ((now.t&1)==1 && sd==0))
- next.t=now.t+1;
- else
- next.t=now.t+2;
- hash[next.ni][next.nj]=1;
- hp.push(next);
- }
- }
- return 0;
- }
- int main()
- {
- bool flag;
- int i,j,ret;
- while(scanf("%d %d",&n,&m)!=EOF)
- {
- getchar(); flag=0;
- for(i=0;i<n;i++)
- {
- gets(ma[i]);
- for(j=0;j<m && !flag;j++)
- if(ma[i][j]=='S'){
- now.ni=i;
- now.nj=j;
- now.t=0;
- flag=1;
- }
- }
- ret=bfs();
- printf("%dn",ret);
- }
- return 0;
- }









