[POJ 3317] | Eurce's Blog

博弈树搜索

题意：棋类游戏盘面大小最多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;

}