银河之星(记忆化搜索+9点染色)

Problem 3 银河之星(galaxy.cpp/c/pas)

数据组数不超过10.

这题就是记忆化搜索

9点染色减少状态,map记忆化

b[i][j][k]表示棋子可否从k方向到(i,j)

#include<cstdio>

include<cstdlib>

include<cstring>

include<algorithm>

include<functional>

include<iostream>

include<cmath>

include<map>

using namespace std;

define MAXN (100+10)

define MAXK (10+10)

define MAXDIV (4)

int k,n,m,x2,y2,a[MAXDIV][MAXDIV],b[MAXDIV][MAXDIV][9]; int c[8][2]={{0,1},{0,2},{1,0},{2,0},{1,1},{2,2},{1,2},{2,1}}; //↑↓→←↗↙↘↖ map<long long,int> h; bool is_ok() { int ans=0; for (int i=0;i<3;i++) for (int j=0;j<3;j++) ans=(11ans+a[i][j]); if (h.find(ans)!=h.end()) return 0; return h[ans]=1;
} bool dfs(int x) { /
for (int j=3;j;j--) { for (int i=1;i<=3;i++) cout<<a[i%3][j%3]; cout<<endl; } cout<<endl; / if (!is_ok()) return 0; if (x==1) { if (a[x2][y2]) return 1; else return 0; } for (int i=0;i<3;i++) for (int j=0;j<3;j++) if (a[i][j]) { for (int l=0;l<8;l++) if (a[(i+c[l][0])%3][(j+c[l][1])%3]&&a[(i+2c[l][0])%3][(j+2c[l][1])%3]<b[(i+2c[l][0])%3][(j+2c[l][1])%3][l]) { a[i][j]--;a[(i+c[l][0])%3][(j+c[l][1])%3]--;a[(i+2c[l][0])%3][(j+2c[l][1])%3]++; if (dfs(x-1)) return 1; a[i][j]++;a[(i+c[l][0])%3][(j+c[l][1])%3]++;a[(i+2c[l][0])%3][(j+2*c[l][1])%3]--;

                }                   
        }
return 0;

}
int main()
{
freopen("galaxy.in","r",stdin);
freopen("galaxy.out","w",stdout);
while (scanf("%d%d%d%d%d",&k,&n,&m,&x2,&y2)!=EOF)
{
x2%=3;y2%=3;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
{
int h=((n/3)+(i>0)(i<=n%3)),r=((m/3)+(j>0)(j<=m%3));
//b[i][j][8]=((n/3)+(i>0)(i<=n%3))((m/3)+(j>0)(j<=m%3));
b[i][j][8]=h
r;
if (j!=0) b[i][j][0]=max(r-1,0)h;else b[i][j][0]=rh;
if ((m+1)%3!=j) b[i][j][1]=max(r-1,0)h;else b[i][j][1]=rh;
if (i!=0) b[i][j][2]=max(h-1,0)r;else b[i][j][2]=rh;
if ((n+1)%3!=i) b[i][j][3]=max(h-1,0)r;else b[i][j][3]=rh;
b[i][j][4]=max(r-(j!=0),0)max(h-(i!=0),0);
b[i][j][5]=max(r-((m+1)%3!=j),0)
max(h-((n+1)%3!=i),0);
b[i][j][6]=max(r-((m+1)%3!=j),0)max(h-(i!=0),0);
b[i][j][7]=max(r-(j!=0),0)
max(h-((n+1)%3!=i),0);
}

    for (int i=1;i&lt;=k;i++) 
    {
        int x,y;
        scanf(&quot;%d%d&quot;,&amp;x,&amp;y);
        a[x%3][y%3]++;
    }
    /*
    for (int j=3;j;j--)
    {
        for (int i=1;i&lt;=3;i++)
            cout&lt;&lt;a[i%3][j%3];
        cout&lt;&lt;endl;
    }
    cout&lt;&lt;endl;
    */
    if (dfs(k)) cout&lt;&lt;&quot;Yes\n&quot;;
    else cout&lt;&lt;&quot;No\n&quot;;
    h.clear();
}   
return 0;

}