月度归档：2014年03月

[POJ 3317]

博弈树搜索

题意：棋类游戏盘面大小最多8*8，两方轮流在空格落子，最后计算双方各自的最大4连通区域的大小来判胜负。空格最多10个。

题目数据范围很小，考虑到深度最多为10，一开始直接写了个O(n!)的算法，TLE。然后想明白可以用Alpha-Beta剪枝，还是TLE。最后发现空格最多10个，用位相量不过是4^10个状态，可以剔除重复状态的计算，然后就开始WA了。

持续的不解后……看了看讨论，才发现原来大家的思路都是一样的（卡了哪题都能看到ZaakDov…）。WA的原因正是Alpha-Beta剪枝导致子状态无法达到最优值，从而记录下了错误的状态值。正解是直接记忆化搜索即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,x,y,el,b[8][8],bi;
int mv[4][2]={-1,0, 1,0, 0,-1, 0,1};
char s[8][9];
int q[64][2],qh,qt;
char d[1<<20];

struct E
{
    int x,y,b;
}e[10];

bool chk(int i,int j,int k)
{
    return i>-1&&i<n&&j>-1&&j<n&&b[i][j]!=bi&&s[i][j]==k;
}

int calc()
{
    int i,j;
    for(i=j=0;i<el;i++)
        j=(j<<2)+s[e[i].x][e[i].y];
    return j;
}

int bfs(int i,int j)
{
    int k=s[i][j],l=0,ml,mi,mj;
    b[i][j]=bi;
    qh=qt=0;
    q[qt][0]=i;
    q[qt][1]=j;
    qt++;
    while(qh<qt)
    {
        i=q[qh][0];
        j=q[qh][1];
        qh++;
        l++;
        for(ml=0;ml<4;ml++)
        {
            mi=i+mv[ml][0];
            mj=j+mv[ml][1];
            if(chk(mi,mj,k))
            {
                b[mi][mj]=bi;
                q[qt][0]=mi;
                q[qt][1]=mj;
                qt++;
            }
        }
    }
    return l;
}

int dfs(int ei,int p)
{
    int h,i,j,k,l;
    h=calc();
    if(d[h]!=127)
        return d[h];
    if(ei==el)
    {
        bi++;
        for(i=k=l=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(b[i][j]!=bi)
                {
                    if(s[i][j]==p)
                        k=max(k,bfs(i,j));
                    else
                        l=max(l,bfs(i,j));
                }
            }
        }
        return k-l;
    }
    for(i=0,j=-100;i<el;i++)
    {
        if(!e[i].b)
        {
            s[e[i].x][e[i].y]=p;
            e[i].b=1;
            k=dfs(ei+1,p^1);
            e[i].b=0;
            if(-k>j)
            {
                j=-k;
                if(!ei)
                {
                    x=e[i].x;
                    y=e[i].y;
                }
            }
            s[e[i].x][e[i].y]=2;
        }
    }
    return d[h]=j;
}

void solve()
{
    int i,j,k,l;
    el=bi=0;
    memset(b,0,sizeof b);
    memset(d,127,sizeof d);
    for(i=k=l=0;i<n;i++)
    {
        scanf("%s",s[i]);
        for(j=0;j<n;j++)
        {
            if(s[i][j]=='0')
            {
                k++;
                s[i][j]=0;
            }
            else if(s[i][j]=='1')
            {
                l++;
                s[i][j]=1;
            }
            else
            {
                e[el].x=i;
                e[el].y=j;
                e[el].b=0;
                el++;
                s[i][j]=2;
            }
        }
    }
    k=dfs(0,k==l?0:1);
    printf("(%d,%d) %d\n",x,y,k);
}

int main()
{
    while(~scanf("%d",&n)&&n)
        solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,x,y,el,b[8][8],bi;

int mv[4][2]={-1,0, 1,0, 0,-1, 0,1};

char s[8][9];

int q[64][2],qh,qt;

char d[1<<20];

struct E

{

int x,y,b;

}e[10];

bool chk(int i,int j,int k)

{

return i>-1&&i<n&&j>-1&&j<n&&b[i][j]!=bi&&s[i][j]==k;

}

int calc()

{

int i,j;

for(i=j=0;i<el;i++)

j=(j<<2)+s[e[i].x][e[i].y];

return j;

}

int bfs(int i,int j)

{

int k=s[i][j],l=0,ml,mi,mj;

b[i][j]=bi;

qh=qt=0;

q[qt][0]=i;

q[qt][1]=j;

qt++;

while(qh<qt)

{

i=q[qh][0];

j=q[qh][1];

qh++;

l++;

for(ml=0;ml<4;ml++)

{

mi=i+mv[ml][0];

mj=j+mv[ml][1];

if(chk(mi,mj,k))

{

b[mi][mj]=bi;

q[qt][0]=mi;

q[qt][1]=mj;

qt++;

}

return l;

}

int dfs(int ei,int p)

{

int h,i,j,k,l;

h=calc();

if(d[h]!=127)

return d[h];

if(ei==el)

{

bi++;

for(i=k=l=0;i<n;i++)

{

for(j=0;j<n;j++)

{

if(b[i][j]!=bi)

{

if(s[i][j]==p)

k=max(k,bfs(i,j));

else

l=max(l,bfs(i,j));

}

return k-l;

}

for(i=0,j=-100;i<el;i++)

{

if(!e[i].b)

{

s[e[i].x][e[i].y]=p;

e[i].b=1;

k=dfs(ei+1,p^1);

e[i].b=0;

if(-k>j)

{

j=-k;

if(!ei)

{

x=e[i].x;

y=e[i].y;

}

s[e[i].x][e[i].y]=2;

}

return d[h]=j;

}

void solve()

{

int i,j,k,l;

el=bi=0;

memset(b,0,sizeof b);

memset(d,127,sizeof d);

for(i=k=l=0;i<n;i++)

{

scanf("%s",s[i]);

for(j=0;j<n;j++)

{

if(s[i][j]=='0')

{

k++;

s[i][j]=0;

}

else if(s[i][j]=='1')

{

l++;

s[i][j]=1;

}

else

{

e[el].x=i;

e[el].y=j;

e[el].b=0;

el++;

s[i][j]=2;

}

k=dfs(0,k==l?0:1);

printf("(%d,%d) %d\n",x,y,k);

}

int main()

{

while(~scanf("%d",&n)&&n)

solve();

return 0;

}

8th BCPC & DevArt

发表回复

过去的一周里做了两个完全不同的比赛，分别是准备了很久的14年北邮校赛，以及临时决定参加的DevArt。前者只是一个周末就结束了，而后者则是花费我5天的时间不断完善。

先说说校赛吧。

读研以来，自己一直看重的还是算法和数学方面的训练。但由于已经没机会参加ICPC了，只能选一些常规比赛来检验自己的实力。而其中让人最有参与感的，莫过于本校学生自己组织的一年一度的校赛了。还记得去年研一的时候第一次参赛，那时候POJ还不到100题，算法导论只看了一半多。临场1个多小时做完3道简单题后，就一直卡在一题模拟题上，整整3个多小时，不断的WA。看着坐在我们旁边一队最后一小时连过3题，并最终拿到金奖（当时4题前7的队伍是金），差一名的我们只能拿银，心理一直无法释怀。

短短一年，很快又过去了。到现在为止，POJ 342题，具体数学读了一半，对各种算法都有一定的初步了解。终于可以挺直胸膛再次站上赛场。依然是与qoshi和usozki组队，这次的队伍名是Srotaidalg_Lufegnev，也即Vengeful Gladiators。比赛的过程，回想起来好像更多是一直在相互打闹……读好的题目大多都没什么障碍的很快过掉，除了那道K题。大概离结束还有一个多小时，我们已经过了5题，排名由于有外校队伍所以无法确定，手里读清并写完的只有一道K题，但交了多次还是WA。不断的思考，一直盯着提问版面看有没有相关的提问、澄清。考虑了多种可能的情况，一一尝试，但都一一错误。从怀疑思路本身有问题一路追溯到程序本身是否有错，反复检查、确认，但都无法找出原因。最后还是usozki想到，数据本身可能并不合法，也即命题人存在失误。时间不多了，修改一下加一个判断，提交。短暂的pending之后，终于返回一个AC，这时离比赛最后结束只剩不到10分钟。

当晚的颁奖仪式前，qoshi发现我们前面的队全都是外校队。也就是说，我们拿到了这次校赛的冠军。颁奖会上很嚣张的戴着glass就过去了……也见到了久违的CAPITAL。最后的奖品是给了每人一个“马化腾”公仔……以及一个完全用不着的罗技鼠标：

公仔是已经送出去了哈，看到这篇文章又想要鼠标的就来找我吧~ 最后也上一张气势磅礴的气球照：

接下来说说DevArt。

这是校赛正赛前一天跟着学校的Google Camp一起去谷歌北京总部玩时了(cai)解(dao)到(di)的(lei)。所谓DevArt，就是Google在全球范围内组织的，鼓励艺术家们通过编程进行艺术创作的比赛。然而，在中国这一活动的开展很不顺利。官方的宣传主要针对中央美术学院的学生，并组织了一些程序员进行协助（每个项目要求最多两人）。但是一个月过去了，很多项目都无法进行，不少人放弃了参赛。比赛是北京时间29号凌晨2点结束的，但直到当天（3月22号）仍没有人能完成一个完整的项目，正顺利进行的也屈指可数。

大概了解了下情况后，我们很快发现自己是被拉来临时救场的……稍微浏览了下DevArt官网上展出的项目，确实有不少很赞的作品，包括使用四轴飞行器结合延长曝光拍摄的空中光弧、分析图画色彩并进行空间可视化、用机械臂控制画笔让大家通过手机、平板等软件绘同一幅画等等等等……真是好酷炫……

嗯，然后也听了一下美院那边学生对自己项目的介绍。其中有一位的想法大概是这样的：自然界有其自身的组成规律，而河流作为自然界中庞大的存在，如同人体经络，循环往复汇成错综复杂的网络。我们希望赋予其新的定义，通过建立一组规则来以声乐的方式阐述每一支河流的独特之处。

听起来很棒，对吧？不过和她合作的人2个多星期以来都一直推脱很忙，如此大概难以按时完成。一起来的朋友都比较感兴趣，就也讨论了下细节。一边自己也在想，我能不能做到呢？语言方面，基本上只会C++，以及用Matlab作简单的图像处理，再就是刚学了一点皮毛的OpenCV。实话说，技术确实不是很扎实呢……但至少，时间安排方面倒是可行的，校赛过后暂时也不太需要忙别的。

那就稍微尝试一下吧。

接下来的5天，从周一到周五，一直都在写这个项目。很久没写这样开放性的程序了。由于搭档并非计算机专业，因此所有的技术细节都要自己敲定，这也正和我意。从一开始的如何抓取google map图像，到如何判断河流是否存在以及找上下游位置，再到确定河流如何流动、在时序上对各个帧和音符进行相应处理等等等等……很久没有这么疯狂的google了。其中最棘手的问题在于如何播放声音，OS X上的系统发声调用非常复杂，是一个叫做AudioQueue的技术，最后还是搜了官方的sample code改了一下用的。当然也有很多解决不了的问题……比如搭档一开始的设想是河流的发声应该由河流本身特点确定，这个我并没有想到特别好的实现方案……另外就是，河流的分支对应着和弦以及其他音色等等的设想（真的很棒哦）……我也没有能力给予实现……

做项目的过程中，也得知对方才18岁，但已经在读大二了……总能给我一种超出其年龄的成熟感。由于之前并没有接触过学艺术的学生，一直也在留心对她进行观察。即使愚钝如我，也能隐约察觉，她对“美”确实有独特的感知能力。而就其性格而言，貌似也是不愿轻易服输的一个人，虽然这周是结课周，并且周末还要去香港，却始终在和我一起跟进这个项目，好像每天也都是深夜还在交流，第二天又接着早起的节奏。

和这样的人一起合作，真的很享受。

最后，还是赶在周六凌晨之前，基本做出了一个完整的项目。最上面Cover的正是艺术家搭档精心修改的结果，还不错吧……？

项目期间也遇到了一些意料之外的Bug，包括DevArt官网上post信息出错，youtube视频上传bug等等……后者是由于我常规方式上传不了（VPN突然被禁，GoAgent又时好时坏）后，发现可以把邮件发给指定的邮箱作为“手机上传”方式上传。结果，我一封邮件过去，系统就悲剧了。每隔1小时就说我成功上传了一个视频，然后狂发邮件给我……到目前为止已经莫名其妙多了24次的额外上传了，feedback过去也不理我，哎：

最后，为了感谢各位读到这里，也附送一些周二在央美那边参观双年展的照片：

[POJ 3133]

发表回复

Manhattan Wiring

插头DP

题意：给出一个最多9*9的格盘描述，其中有两个2和两个3，求将两个2和3分别用不相交的线段相连所需的最短线长。线不能交叉且仅能经过空格。

明确是插头DP后，首先要考虑如何表示状态。这题特殊之处在于线段有两条，且需要和指定的端点相连。那么，最关键的是确定如何表达有效的终状态。

考虑以下解方案：用0表示空插头，2和3分别有相应插头。那么这里每个位置需要2bit，总共是2*10=20bit。再用最低的4个bit分别表示4个端点是否有连接，由此便能用一个int来表示轮廓线状态u。判断终状态时，直接用u==15即可。其正确性在于，题目所求的是最短线长，那么若4个端点已连，且当前没有空线头，则端点间必定已存在连线。同时也可能存在不与任何端点相连的线环，但线环仅仅是增加了总线长，不影响正确性。

实现方面，由于状态数为1<<24，若直接存下各个状态的最短线长，只能用char数组，由于题目数据范围不大，这是可行的。但一开始还是用了int数组和hash处理（u%10007)。按理说直接访问状态应该要比hash快，但事实上后者比前者要快两倍多（500ms VS 1600MS）。猜测是由于hash过后状态值较为接近，内存访问要更为集中。虽然再加一些状态剪枝应该可以更快……但当前的代码长度竟已超过了5K，实在是不太明白那些2K左右跑出300ms的代码是怎么写的…… =(

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define M 1<<24
#define MS 1<<20

int n,m,ans;
int x2s,y2s,x2e,y2e,x3s,y3s,x3e,y3e;
int mem3[MS],mem4[MS];
int *st1,*st2,s1l,s2l;
int b[9][9];
char mem1[M],mem2[M],*u1,*u2,ms[M],msij;

int chk(int i,int j)
{
    return i==n||j==m||b[i][j]==1;
}

bool chs(int i,int j,int &u,int v)
{
    if(b[i][j]==v)
    {
        if(i==x2s&&j==y2s&&!(u&8))
        {
            u|=8;
            return 1;
        }
        if(i==x2e&&j==y2e&&!(u&4))
        {
            u|=4;
            return 1;
        }
        if(i==x3s&&j==y3s&&!(u&2))
        {
            u|=2;
            return 1;
        }
        if(i==x3e&&j==y3e&&!(u&1))
        {
            u|=1;
            return 1;
        }
    }
    return 0;
}

void adde(int u,int ud)
{
    if(u==15)
    {
        ans=min(ans,ud);
        return;
    }
    else if(ud>=ans)
        return;
    if(ms[u]!=msij)
    {
        ms[u]=msij;
        u2[u]=ud;
        st2[s2l++]=u;
    }
    else
        u2[u]=min(u2[u],(char)ud);
}

void init()
{
    int i,j,k,l;
    ans=0x7fffffff;
    x2s=y2s=x2e=y2e=x3s=y3s=x3e=y3e=-1;
    u1=mem1,u2=mem2;
    st1=mem3,st2=mem4,s1l=s2l=0;
    memset(ms,-1,sizeof ms);
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            scanf("%d",&b[i][j]);
            if(b[i][j]==2)
            {
                if(x2s==-1)
                    x2s=i,y2s=j;
                else if(x2e==-1)
                    x2e=i,y2e=j;
                else
                    ans=-1;
            }
            else if(b[i][j]==3)
            {
                if(x3s==-1)
                    x3s=i,y3s=j;
                else if(x3e==-1)
                    x3e=i,y3e=j;
                else
                    ans=-1;
            }
        }
    }
}

int gt(int u,int l)
{
    return (u>>(4+2*(m-l)))&3;
}

void st(int &u,int l,int v)
{
    u&=~(3<<(4+2*(m-l)));
    u|=v<<(4+2*(m-l));
}

void solve()
{
    if(ans==-1)
    {
        puts("0");
        return;
    }
    int i,j,k,l;
    int v1,v2,u,uu,ud;
    u1[0]=0;
    st1[s1l++]=0;
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            msij=i*m+j;
            if(b[i][j]==1)
                continue;
            k=chk(i+1,j)*2+chk(i,j+1);
            while(s1l)
            {
                u=st1[--s1l];
                ud=u1[u];
                v1=gt(u,m);
                v2=gt(u,j);
                if(!v1&&!v2)
                {
                    if(b[i][j]==0)
                    {
                        adde(u,ud);
                        if(k==0)
                        {
                            uu=u;
                            st(uu,j,2);
                            st(uu,m,2);
                            adde(uu,ud+1);
                            uu=u;
                            st(uu,j,3);
                            st(uu,m,3);
                            adde(uu,ud+1);
                        }
                    }
                    else if(b[i][j]>1)
                    {
                        uu=u;
                        if((k==0||k==1)&&chs(i,j,uu,b[i][j]))
                        {
                            st(uu,j,b[i][j]);
                            st(uu,m,0);
                            adde(uu,ud);
                        }
                        uu=u;
                        if((k==0||k==2)&&chs(i,j,uu,b[i][j]))
                        {
                            st(uu,j,0);
                            st(uu,m,b[i][j]);
                            adde(uu,ud);
                        }
                    }
                }
                else if(!v1||!v2)
                {
                    if(b[i][j]>1)
                    {
                        uu=u;
                        if(chs(i,j,uu,v1+v2))
                        {
                            st(uu,j,0);
                            st(uu,m,0);
                            adde(uu,ud);
                        }
                    }
                    else if(b[i][j]==0)
                    {
                        if(k==0||k==1)
                        {
                            uu=u;
                            st(uu,j,v1+v2);
                            st(uu,m,0);
                            adde(uu,ud+1);
                        }
                        if(k==0||k==2)
                        {
                            uu=u;
                            st(uu,j,0);
                            st(uu,m,v1+v2);
                            adde(uu,ud+1);
                        }
                    }
                }
                else if(v1==v2)
                {
                    if(b[i][j]==0)
                    {
                        uu=u;
                        st(uu,j,0);
                        st(uu,m,0);
                        adde(uu,ud+1);
                    }
                }
            }
            swap(u1,u2);
            swap(st1,st2);
            s1l=s2l;
            s2l=0;
        }
    }
    printf("%d\n",ans==0x7fffffff?0:ans+2);
}

int main()
{
    while(~scanf("%d%d",&n,&m)&&n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 1<<24

#define MS 1<<20

int n,m,ans;

int x2s,y2s,x2e,y2e,x3s,y3s,x3e,y3e;

int mem3[MS],mem4[MS];

int *st1,*st2,s1l,s2l;

int b[9][9];

char mem1[M],mem2[M],*u1,*u2,ms[M],msij;

int chk(int i,int j)

{

return i==n||j==m||b[i][j]==1;

}

bool chs(int i,int j,int &u,int v)

{

if(b[i][j]==v)

{

if(i==x2s&&j==y2s&&!(u&8))

{

u|=8;

return 1;

}

if(i==x2e&&j==y2e&&!(u&4))

{

u|=4;

return 1;

}

if(i==x3s&&j==y3s&&!(u&2))

{

u|=2;

return 1;

}

if(i==x3e&&j==y3e&&!(u&1))

{

u|=1;

return 1;

}

return 0;

}

void adde(int u,int ud)

{

if(u==15)

{

ans=min(ans,ud);

return;

}

else if(ud>=ans)

return;

if(ms[u]!=msij)

{

ms[u]=msij;

u2[u]=ud;

st2[s2l++]=u;

}

else

u2[u]=min(u2[u],(char)ud);

}

void init()

{

int i,j,k,l;

ans=0x7fffffff;

x2s=y2s=x2e=y2e=x3s=y3s=x3e=y3e=-1;

u1=mem1,u2=mem2;

st1=mem3,st2=mem4,s1l=s2l=0;

memset(ms,-1,sizeof ms);

for(i=0;i<n;i++)

{

for(j=0;j<m;j++)

{

scanf("%d",&b[i][j]);

if(b[i][j]==2)

{

if(x2s==-1)

x2s=i,y2s=j;

else if(x2e==-1)

x2e=i,y2e=j;

else

ans=-1;

}

else if(b[i][j]==3)

{

if(x3s==-1)

x3s=i,y3s=j;

else if(x3e==-1)

x3e=i,y3e=j;

else

ans=-1;

}

int gt(int u,int l)

{

return (u>>(4+2*(m-l)))&3;

}

void st(int &u,int l,int v)

{

u&=~(3<<(4+2*(m-l)));

u|=v<<(4+2*(m-l));

}

void solve()

{

if(ans==-1)

{

puts("0");

return;

}

int i,j,k,l;

int v1,v2,u,uu,ud;

u1[0]=0;

st1[s1l++]=0;

for(i=0;i<n;i++)

{

for(j=0;j<m;j++)

{

msij=i*m+j;

if(b[i][j]==1)

continue;

k=chk(i+1,j)*2+chk(i,j+1);

while(s1l)

{

u=st1[--s1l];

ud=u1[u];

v1=gt(u,m);

v2=gt(u,j);

if(!v1&&!v2)

{

if(b[i][j]==0)

{

adde(u,ud);

if(k==0)

{

uu=u;

st(uu,j,2);

st(uu,m,2);

adde(uu,ud+1);

uu=u;

st(uu,j,3);

st(uu,m,3);

adde(uu,ud+1);

}

else if(b[i][j]>1)

{

uu=u;

if((k==0||k==1)&&chs(i,j,uu,b[i][j]))

{

st(uu,j,b[i][j]);

st(uu,m,0);

adde(uu,ud);

}

uu=u;

if((k==0||k==2)&&chs(i,j,uu,b[i][j]))

{

st(uu,j,0);

st(uu,m,b[i][j]);

adde(uu,ud);

}

else if(!v1||!v2)

{

if(b[i][j]>1)

{

uu=u;

if(chs(i,j,uu,v1+v2))

{

st(uu,j,0);

st(uu,m,0);

adde(uu,ud);

}

else if(b[i][j]==0)

{

if(k==0||k==1)

{

uu=u;

st(uu,j,v1+v2);

st(uu,m,0);

adde(uu,ud+1);

}

if(k==0||k==2)

{

uu=u;

st(uu,j,0);

st(uu,m,v1+v2);

adde(uu,ud+1);

}

else if(v1==v2)

{

if(b[i][j]==0)

{

uu=u;

st(uu,j,0);

st(uu,m,0);

adde(uu,ud+1);

}

swap(u1,u2);

swap(st1,st2);

s1l=s2l;

s2l=0;

}

printf("%d\n",ans==0x7fffffff?0:ans+2);

}

int main()

{

while(~scanf("%d%d",&n,&m)&&n)

{

init();

solve();

}

return 0;

}

[Ural 1519]

发表回复

Formula 1

插头DP

题意：给出一个最多12*12的地形描述，问有多少方式在其上建一条F1赛道。一条F1赛道为仅横竖相连且覆盖所有空地的一个环。

参考了陈丹琦的《基于连通性状态压缩的动态规划问题》，插头+轮廓线扫描。虽然论文已经给出了基本思路，但仍存在一些特殊情况，如：

0   1   2   3   4   5   6   7
* ( (   (   )   (   )   )   )

1 2	0 1 2 3 4 5 6 7 * ( ( ( ) ( ) ) )

应转变为

0   1   2   3   4   5   6   7
*   * * (   )   (   )   (   )

1 2	0 1 2 3 4 5 6 7 * * * ( ) ( ) ( )

我用了很长时间才发现这一点。

实现方面，一开始打算全部用位运算，但发现存储的时候状态数太多，无法直接开大数组存，于是又转成3进制。每次更新下一个格点的状态值时，交换内存指针，根据相应内存位置标记来判断是否置0，这样就避免了每次对大数组进行memset。另外，使用了栈来非重复地保存各状态（仅当计数值为0时入栈），避免了每次扫描整个计数数组。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define M 1594323

ll n,m,ei,ej,pn,ans;
ll mem1[M],mem2[M],mem3[M],mem4[M];
ll *mp1,*mp2,*st1,*st2,sl1,sl2;
char s[12][13],ms[M],msij;

void init()
{
    ll i,j;
    ei=ej=-1;
    ans=0;
    sl1=0;
    memset(ms,-1,sizeof ms);
    mp1=mem1;
    mp2=mem2;
    st1=mem3;
    st2=mem4;
    for(i=pn=0;i<n;i++)
    {
        scanf("%s",s[i]);
        for(j=0;j<m;j++)
        {
            if(s[i][j]=='.')
            {
                pn++;
                ei=i;
                ej=j;
            }
        }
    }
}

ll enc(ll u)
{
    ll i,l;
    for(i=l=0;l<=m;l++)
    {
        i=i*3+(u&3);
        u>>=2;
    }
    return i;
}

ll dec(ll i)
{
    ll u,l;
    for(u=l=0;l<=m;l++)
    {
        u=(u<<2)+i%3;
        i/=3;
    }
    return u;
}

ll chk(ll i,ll j)
{
    if(i==n||j==m||s[i][j]!='.')
        return 1;
    return 0;
}

ll gt(ll u,ll j)
{
    return (u>>(2*(m-j)))&3;
}

void st(ll &u,ll j,ll v)
{
    u&=~(3LL<<(2*(m-j)));
    u|=v<<(2*(m-j));
}

void ins(ll u,ll ud)
{
    ll ml=enc(u);
    if(ms[ml]!=msij)
    {
        mp2[ml]=0;
        ms[ml]=msij;
    }
    if(!mp2[ml])
        st2[sl2++]=ml;
    mp2[ml]+=ud;
}

void solve()
{
    if(ei==-1||(pn&1))
    {
        puts("0");
        return;
    }
    ll i,j,k,l,ul,cnt;
    ll u,ud,v1,v2;
    ll ms=1,ml;
    for(l=0;l<=m;l++)
        ms*=3;
    mp1[enc(0)]=1;
    st1[sl1++]=enc(0);
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            msij=i*m+j;
            if(s[i][j]=='*')
                continue;
            k=(chk(i+1,j)<<1)+(chk(i,j+1));
            sl2=0;
            while(sl1)
            {
                ml=st1[--sl1];
                u=dec(ml);
                ud=mp1[ml];
                v1=gt(u,m);
                v2=gt(u,j);
                if(!v1&&!v2)
                {
                    if(k==0)
                    {
                        st(u,j,1);
                        st(u,m,2);
                        ins(u,ud);
                    }
                }
                else if(!v1||!v2)
                {
                    if(k==0||k==1)
                    {
                        st(u,j,v1+v2);
                        st(u,m,0);
                        ins(u,ud);
                    }
                    if(k==0||k==2)
                    {
                        st(u,j,0);
                        st(u,m,v1+v2);
                        ins(u,ud);
                    }
                }
                else if(v1!=v2)
                {
                    if(v1==1&&v2==2&&(i!=ei||j!=ej))
                        continue;
                    if(v1==1&&v2==2&&i==ei&&j==ej)
                        ans+=ud;
                    st(u,j,0);
                    st(u,m,0);
                    ins(u,ud);
                }
                else if(v1==1)
                {
                    st(u,j,0);
                    st(u,m,0);
                    for(l=j+1,cnt=0;l<m;l++)
                    {
                        ul=gt(u,l);
                        if(ul==1)
                            cnt++;
                        else if(ul==2)
                        {
                            if(!cnt)
                                break;
                            cnt--;
                        }
                    }
                    st(u,l,1);
                    ins(u,ud);
                }
                else
                {
                    st(u,j,0);
                    st(u,m,0);
                    for(l=j-1,cnt=0;l>-1;l--)
                    {
                        ul=gt(u,l);
                        if(ul==2)
                            cnt++;
                        else if(ul==1)
                        {
                            if(!cnt)
                                break;
                            cnt--;
                        }
                    }
                    st(u,l,2);
                    ins(u,ud);
                }
            }
            swap(mp1,mp2);
            swap(st1,st2);
            sl1=sl2;
        }
    }
    printf("%lld\n",ans);
}

int main()
{
    while(~scanf("%lld%lld",&n,&m))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define M 1594323

ll n,m,ei,ej,pn,ans;

ll mem1[M],mem2[M],mem3[M],mem4[M];

ll *mp1,*mp2,*st1,*st2,sl1,sl2;

char s[12][13],ms[M],msij;

void init()

{

ll i,j;

ei=ej=-1;

ans=0;

sl1=0;

memset(ms,-1,sizeof ms);

mp1=mem1;

mp2=mem2;

st1=mem3;

st2=mem4;

for(i=pn=0;i<n;i++)

{

scanf("%s",s[i]);

for(j=0;j<m;j++)

{

if(s[i][j]=='.')

{

pn++;

ei=i;

ej=j;

}

ll enc(ll u)

{

ll i,l;

for(i=l=0;l<=m;l++)

{

i=i*3+(u&3);

u>>=2;

}

return i;

}

ll dec(ll i)

{

ll u,l;

for(u=l=0;l<=m;l++)

{

u=(u<<2)+i%3;

i/=3;

}

return u;

}

ll chk(ll i,ll j)

{

if(i==n||j==m||s[i][j]!='.')

return 1;

return 0;

}

ll gt(ll u,ll j)

{

return (u>>(2*(m-j)))&3;

}

void st(ll &u,ll j,ll v)

{

u&=~(3LL<<(2*(m-j)));

u|=v<<(2*(m-j));

}

void ins(ll u,ll ud)

{

ll ml=enc(u);

if(ms[ml]!=msij)

{

mp2[ml]=0;

ms[ml]=msij;

}

if(!mp2[ml])

st2[sl2++]=ml;

mp2[ml]+=ud;

}

void solve()

{

if(ei==-1||(pn&1))

{

puts("0");

return;

}

ll i,j,k,l,ul,cnt;

ll u,ud,v1,v2;

ll ms=1,ml;

for(l=0;l<=m;l++)

ms*=3;

mp1[enc(0)]=1;

st1[sl1++]=enc(0);

for(i=0;i<n;i++)

{

for(j=0;j<m;j++)

{

msij=i*m+j;

if(s[i][j]=='*')

continue;

k=(chk(i+1,j)<<1)+(chk(i,j+1));

sl2=0;

while(sl1)

{

ml=st1[--sl1];

u=dec(ml);

ud=mp1[ml];

v1=gt(u,m);

v2=gt(u,j);

if(!v1&&!v2)

{

if(k==0)

{

st(u,j,1);

st(u,m,2);

ins(u,ud);

}

else if(!v1||!v2)

{

if(k==0||k==1)

{

st(u,j,v1+v2);

st(u,m,0);

ins(u,ud);

}

if(k==0||k==2)

{

st(u,j,0);

st(u,m,v1+v2);

ins(u,ud);

}

else if(v1!=v2)

{

if(v1==1&&v2==2&&(i!=ei||j!=ej))

continue;

if(v1==1&&v2==2&&i==ei&&j==ej)

ans+=ud;

st(u,j,0);

st(u,m,0);

ins(u,ud);

}

else if(v1==1)

{

st(u,j,0);

st(u,m,0);

for(l=j+1,cnt=0;l<m;l++)

{

ul=gt(u,l);

if(ul==1)

cnt++;

else if(ul==2)

{

if(!cnt)

break;

cnt--;

}

st(u,l,1);

ins(u,ud);

}

else

{

st(u,j,0);

st(u,m,0);

for(l=j-1,cnt=0;l>-1;l--)

{

ul=gt(u,l);

if(ul==2)

cnt++;

else if(ul==1)

{

if(!cnt)

break;

cnt--;

}

st(u,l,2);

ins(u,ud);

}

swap(mp1,mp2);

swap(st1,st2);

sl1=sl2;

}

printf("%lld\n",ans);

}

int main()

{

while(~scanf("%lld%lld",&n,&m))

{

init();

solve();

}

return 0;

}

在ural上用VS 2010只能跑出0.6S左右的时间。瓶颈应该是慢在位向量和3进制间转换上面，但也没有想到太好的优化了……

ps：小小感慨一下，连这种问题都可以DP，实在是不可思议。

[POJ 3131]

发表回复

Cubic Eight-Puzzle

双向广搜

题意：有9个格子，其中8个格子有立方体。立方体相对的两面颜色相同，分别为红、白、蓝色。若某立方体相邻格为空，则该立方体可以向该方向滚动。给定初始状态，问最少滚动多少次（不大于30），可以使各盘格为指定的颜色。

类似这种搜索题，最关键的还是状态的表达。立方体的姿态可以由顶面和正面的颜色来确定，共有6种。有9个格子，考虑使用每个格子3bit，那么搜索空间的规模就是2^(3*9)，大概是1亿。接下来，考虑如何判重。如果使用一个位来表示一个状态，总共需要的内存大小为2^24bytes，也就16MB，是可行的。直接开一个char c[1<<24]，连hash都省了。由此，可以保证所有的操作全部为位运算。接下来考虑搜索的形式，一般来说双向广搜，两边的深度限制相同时可以最大化降低复杂度，但该题反向搜索时起始状态较多（256个状态），层数不深时规模已经很大。因此，正向搜索深度设为20，反向为10。正向搜索完后如果找到解，则直接输出，否则才执行反向搜索。

#include<cstdio>
#include<cstring>

#define M 500000
#define D 20

int eh,el,x,y,b,bm=0x06db6db6,xe,ye,be,ans;
int mv[4][2]={-1,0,1,0,0,-1,0,1},t[128];
int mu[8][4]={0,0,0,0, 0,0,0,0, 7,7,5,5, 4,4,6,6, 
    3,3,7,7, 6,6,2,2, 5,5,3,3, 2,2,4,4};
char s[2],c[1<<24],cr[1<<24];

struct E
{
    int x,y,b,d;
}e[M];

inline int getl(int x,int y)
{
    return ((3-y)<<3)+(3-y)+((3-x)<<1)+(3-x);
}

void init()
{
    int i,j,k,l;
    eh=el=b=be=0;
    ans=0x7fffffff;
    memset(c,0,sizeof c);
    memset(cr,0,sizeof cr);
    for(i=l=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            b=(b<<3)+5;
            scanf("%s",s);
            be=(be<<3)+t[s[0]];
            if(s[0]=='E')
            {
                xe=j+1;
                ye=i+1;
            }
        }
    }
    b&=~(7<<getl(x,y));
}

inline bool chk(int x,int y,int b,char c[])
{
    return x>0&&x<4&&y>0&&y<4&&!(c[b>>3]&(1<<(b&7)));
}

inline int calc(int bz,int xz,int yz,int x,int y,int l)
{
    int i,j,k,l1,l2;
    l1=getl(xz,yz); l2=getl(x,y);
    k=mu[(bz&(7<<l2))>>l2][l];
    bz=(bz&~(7<<l2))+(k<<l1);
    return bz;
}

void bfs()
{
    int i,j,k,l;
    e[el].x=x;
    e[el].y=y;
    e[el].b=b;
    e[el].d=0;
    c[e[el].b>>3]|=(1<<(e[el].b&7));
    el++;
    while(eh!=el)
    {
        i=eh++;
        if(e[i].d==D)
            continue;
        for(l=0;l<4;l++)
        {
            e[el].x=e[i].x+mv[l][0];
            e[el].y=e[i].y+mv[l][1];
            e[el].b=calc(e[i].b,e[i].x,e[i].y,
                    e[el].x,e[el].y,l);
            e[el].d=e[i].d+1;
            if(chk(e[el].x,e[el].y,e[el].b,c))
            {
                c[e[el].b>>3]|=(1<<(e[el].b&7));
                if((e[el].b&bm)==be)
                {
                    ans=e[el].d;
                    return;
                }
                el++;
            }
        }
    }
}

void rbfs()
{
    int i,j,k,l;
    l=1<<(getl(xe,ye)/3);
    eh=el=0;
    for(i=0;i<512;i++)
    {
        if(i&l)
            continue;
        e[el].x=xe;
        e[el].y=ye;
        e[el].b=be;
        e[el].d=0;
        for(j=i,k=0;j;j>>=1,k+=3)
        {
            e[el].b+=(j&1)<<k;
        }
        cr[e[el].b>>3]|=(1<<(e[el].b&7));
        el++;
    }
    while(eh!=el)
    {
        i=eh++;
        if(e[i].d==30-D)
            continue;
        for(l=0;l<4;l++)
        {
            e[el].x=e[i].x+mv[l][0];
            e[el].y=e[i].y+mv[l][1];
            e[el].b=calc(e[i].b,e[i].x,e[i].y,
                    e[el].x,e[el].y,l);
            e[el].d=e[i].d+1;
            if(chk(e[el].x,e[el].y,e[el].b,cr))
            {
                cr[e[el].b>>3]|=(1<<(e[el].b&7));
                if(!chk(e[el].x,e[el].y,e[el].b,c))
                {
                    ans=e[el].d+D;
                    return;
                }
                el++;
            }
        }
    }
}

void solve()
{
    if((b&bm)==be)
    {
        puts("0");
        return;
    }
    bfs();
    if(ans<0x7fffffff)
    {
        printf("%d\n",ans);
        return;
    }
    rbfs();
    printf("%d\n",ans==0x7fffffff?-1:ans);
}

int main()
{
    t['R']=2; t['W']=4; t['B']=6;
    while(~scanf("%d%d",&x,&y)&&x)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

#include<cstdio>

#include<cstring>

#define M 500000

#define D 20

int eh,el,x,y,b,bm=0x06db6db6,xe,ye,be,ans;

int mv[4][2]={-1,0,1,0,0,-1,0,1},t[128];

int mu[8][4]={0,0,0,0, 0,0,0,0, 7,7,5,5, 4,4,6,6,

3,3,7,7, 6,6,2,2, 5,5,3,3, 2,2,4,4};

char s[2],c[1<<24],cr[1<<24];

struct E

{

int x,y,b,d;

}e[M];

inline int getl(int x,int y)

{

return ((3-y)<<3)+(3-y)+((3-x)<<1)+(3-x);

}

void init()

{

int i,j,k,l;

eh=el=b=be=0;

ans=0x7fffffff;

memset(c,0,sizeof c);

memset(cr,0,sizeof cr);

for(i=l=0;i<3;i++)

{

for(j=0;j<3;j++)

{

b=(b<<3)+5;

scanf("%s",s);

be=(be<<3)+t[s[0]];

if(s[0]=='E')

{

xe=j+1;

ye=i+1;

}

b&=~(7<<getl(x,y));

}

inline bool chk(int x,int y,int b,char c[])

{

return x>0&&x<4&&y>0&&y<4&&!(c[b>>3]&(1<<(b&7)));

}

inline int calc(int bz,int xz,int yz,int x,int y,int l)

{

int i,j,k,l1,l2;

l1=getl(xz,yz); l2=getl(x,y);

k=mu[(bz&(7<<l2))>>l2][l];

bz=(bz&~(7<<l2))+(k<<l1);

return bz;

}

void bfs()

{

int i,j,k,l;

e[el].x=x;

e[el].y=y;

e[el].b=b;

e[el].d=0;

c[e[el].b>>3]|=(1<<(e[el].b&7));

el++;

while(eh!=el)

{

i=eh++;

if(e[i].d==D)

continue;

for(l=0;l<4;l++)

{

e[el].x=e[i].x+mv[l][0];

e[el].y=e[i].y+mv[l][1];

e[el].b=calc(e[i].b,e[i].x,e[i].y,

e[el].x,e[el].y,l);

e[el].d=e[i].d+1;

if(chk(e[el].x,e[el].y,e[el].b,c))

{

c[e[el].b>>3]|=(1<<(e[el].b&7));

if((e[el].b&bm)==be)

{

ans=e[el].d;

return;

}

el++;

}

void rbfs()

{

int i,j,k,l;

l=1<<(getl(xe,ye)/3);

eh=el=0;

for(i=0;i<512;i++)

{

if(i&l)

continue;

e[el].x=xe;

e[el].y=ye;

e[el].b=be;

e[el].d=0;

for(j=i,k=0;j;j>>=1,k+=3)

{

e[el].b+=(j&1)<<k;

}

cr[e[el].b>>3]|=(1<<(e[el].b&7));

el++;

}

while(eh!=el)

{

i=eh++;

if(e[i].d==30-D)

continue;

for(l=0;l<4;l++)

{

e[el].x=e[i].x+mv[l][0];

e[el].y=e[i].y+mv[l][1];

e[el].b=calc(e[i].b,e[i].x,e[i].y,

e[el].x,e[el].y,l);

e[el].d=e[i].d+1;

if(chk(e[el].x,e[el].y,e[el].b,cr))

{

cr[e[el].b>>3]|=(1<<(e[el].b&7));

if(!chk(e[el].x,e[el].y,e[el].b,c))

{

ans=e[el].d+D;

return;

}

el++;

}

void solve()

{

if((b&bm)==be)

{

puts("0");

return;

}

bfs();

if(ans<0x7fffffff)

{

printf("%d\n",ans);

return;

}

rbfs();

printf("%d\n",ans==0x7fffffff?-1:ans);

}

int main()

{

t['R']=2; t['W']=4; t['B']=6;

while(~scanf("%d%d",&x,&y)&&x)

{

init();

solve();

}

return 0;

}

虽然没有剪枝，但是内存全部静态分配并且大量使用位运算，程序非常的快（久违的刷到了第一）。

Learning OpenCV

发表回复

由于项目需要，最近开始研究OpenCV。

还是依照坏习惯先找本书看，用的教材是学习OpenCV，内容稍旧，翻译质量也一般，但也只有这么一本书可以用了。

在OS X上安装OpenCV有不少方法，先是尝试了下官方的源码然后自己编译安装，安装过程一切顺利，但就是不知道怎么用。于是卸载掉，用brew重新安装，装完了还是不知道怎么用。之后看了这篇，总算懂了。在用XCode建工程，增加头文件搜索路径，并加载OpenCV库之后，总算能正确编译例程了。虽然表面还是熟悉的C++，三两行间却实现了之前难以想象的复杂功能，完全感觉是另一种语言了。另外，这也是第一次用比较“高级”的IDE，自动补全真的是让人很易上瘾。

贴一段书上读取摄像头的小例程，总共18行就完整实现了读入摄像头数据并显示……

#include "highgui.h"

int main()
{
    cvNamedWindow( "Exmaple2", CV_WINDOW_AUTOSIZE );    //打开一个窗口
    CvCapture* capture = cvCreateCameraCapture(0);      //声明一个摄像头输入
    IplImage* frame;                                    //声明一个帧指针
    while (1) {                                         //循环播放新帧
        frame = cvQueryFrame( capture );                //从摄像头读入一帧
        if( !frame ) break;
        cvShowImage( "Example2", frame );               //在窗口显示
        char c = cvWaitKey(33);                         //等待0.033秒，并读取一个字符
        if( c == 27 ) break;                            //如果是"Esc"，则退出
    }
    cvReleaseCapture( &capture );
    cvDestroyWindow( "Example2" );
    return 0;
}

#include "highgui.h"

int main()

{

cvNamedWindow( "Exmaple2", CV_WINDOW_AUTOSIZE ); //打开一个窗口

CvCapture* capture = cvCreateCameraCapture(0); //声明一个摄像头输入

IplImage* frame; //声明一个帧指针

while (1) { //循环播放新帧

frame = cvQueryFrame( capture ); //从摄像头读入一帧

if( !frame ) break;

cvShowImage( "Example2", frame ); //在窗口显示

char c = cvWaitKey(33); //等待0.033秒，并读取一个字符

if( c == 27 ) break; //如果是"Esc"，则退出

}

cvReleaseCapture( &capture );

cvDestroyWindow( "Example2" );

return 0;

}

[POJ 3731]

发表回复

Escape

构造 + 组合

题意：在n*m的网格表示的街道图内，移动时需要走格线，每个交点最多可以经过一次，在交点处可以选择直行或右转。问从起点(0,0)出发到终点(x,y)最多有多少种走法。

这题想了很久也没头绪，然后看了看discuss里有人提示用”转弯次数”+”组合数”分类讨论，然后细心推了一下：从起点到终点之间的路径，总是纵横交错的。并且其中纵向部分，南北两向总是交替出现的；横向部分同理。通过进一步分析可以发现，若确定了一条路径的转弯次数，那么其中横向和纵向的部分是相互独立的，也即该转弯次数对应的路径总数为横向部分的方案数与纵向部分方案数的乘积。横向、纵向的方案数是可以分别通过组合数来计算出来的。在某方向上，每次拐弯的位置必须是交错地位于终点坐标两侧的，那么总方案数即为从两侧选择拐弯位置的总可能数。例如，横向坐标范围0~4，终点在3时，那么横向拐2次弯的总方案数为C(1,1)*C(3,1)，即先从4~4里面选一个位置拐一次，再从0~2里面选一个位置拐一次。不存在拐3次或以上弯的可能性。

到这里为止的推算还算是顺利的，倒是在计算C(n,k)上卡了很久的TLE。考虑了很久如何在模系统中实现除法，未果。于是开始分解质因数再累加，并想了各种优化……但都TLE了。最后才想起来可以利用C(n,k)=C(n-1,k)+C(n-1,k-1)来预处理出整个int C[2002][2002]，于是就AC了。

#include<cstdio>
#include<cstring>
#define M 100000007
#define ll long long

ll x,y,xe,ye,ans;
ll xd[2002],yd[2002];
ll c[2002][2002];

void init()
{
    ll i,j,k,l;
    for(i=0;i<2002;i++)
        for(j=c[i][0]=c[i][i]=1,k=i/2+1;j<k;j++)
            c[i][j]=c[i][i-j]=(c[i-1][j]+c[i-1][j-1])%M;
}

void solve()
{
    if(!xe&&!ye)
    {
        puts("1");
        return;
    }
    ll i,j,k,l;
    ll xl,xr,yb,yt;
    memset(xd,0,sizeof xd);
    memset(yd,0,sizeof yd);
    xl=xe-1; xr=x-xe;
    yb=ye; yt=y-ye;
    if(xe==0)
        xd[0]=1;
    if(ye==0)
        yd[0]=1;
    for(i=1;i<=x+1;i++)
    {
        j=(i-1)/2;
        k=(i-1)-j;
        xd[i]=c[xl][j]*c[xr][k]%M;
    }
    for(i=1;i<=y+1;i++)
    {
        j=(i-1)/2;
        k=(i-1)-j;
        yd[i]=c[yb][j]*c[yt][k]%M;
    }
    ans=yd[0]*xd[0];
    for(i=1;i<=x+1;i++)
        ans=(ans+yd[i]*(xd[i]+xd[i-1]))%M;
    printf("%lld\n",ans);
}

int main()
{
    init();
    scanf("%*d");
    while(~scanf("%lld%lld%lld%lld",&x,&y,&xe,&ye))
        solve();
    return 0;
}

#include<cstdio>

#include<cstring>

#define M 100000007

#define ll long long

ll x,y,xe,ye,ans;

ll xd[2002],yd[2002];

ll c[2002][2002];

void init()

{

ll i,j,k,l;

for(i=0;i<2002;i++)

for(j=c[i][0]=c[i][i]=1,k=i/2+1;j<k;j++)

c[i][j]=c[i][i-j]=(c[i-1][j]+c[i-1][j-1])%M;

}

void solve()

{

if(!xe&&!ye)

{

puts("1");

return;

}

ll i,j,k,l;

ll xl,xr,yb,yt;

memset(xd,0,sizeof xd);

memset(yd,0,sizeof yd);

xl=xe-1; xr=x-xe;

yb=ye; yt=y-ye;

if(xe==0)

xd[0]=1;

if(ye==0)

yd[0]=1;

for(i=1;i<=x+1;i++)

{

j=(i-1)/2;

k=(i-1)-j;

xd[i]=c[xl][j]*c[xr][k]%M;

}

for(i=1;i<=y+1;i++)

{

j=(i-1)/2;

k=(i-1)-j;

yd[i]=c[yb][j]*c[yt][k]%M;

}

ans=yd[0]*xd[0];

for(i=1;i<=x+1;i++)

ans=(ans+yd[i]*(xd[i]+xd[i-1]))%M;

printf("%lld\n",ans);

}

int main()

{

init();

scanf("%*d");

while(~scanf("%lld%lld%lld%lld",&x,&y,&xe,&ye))

solve();

return 0;

}