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=(11*ans+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+2*c[l][0])%3][(j+2*c[l][1])%3]<b[(i+2*c[l][0])%3][(j+2*c[l][1])%3][l])
{
a[i][j]--;a[(i+c[l][0])%3][(j+c[l][1])%3]--;a[(i+2*c[l][0])%3][(j+2*c[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+2*c[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]=r*h;
if ((m+1)%3!=j) b[i][j][1]=max(r-1,0)*h;else b[i][j][1]=r*h;
if (i!=0) b[i][j][2]=max(h-1,0)*r;else b[i][j][2]=r*h;
if ((n+1)%3!=i) b[i][j][3]=max(h-1,0)*r;else b[i][j][3]=r*h;
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<=k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x%3][y%3]++;
}
/*
for (int j=3;j;j--)
{
for (int i=1;i<=3;i++)
cout<<a[i%3][j%3];
cout<<endl;
}
cout<<endl;
*/
if (dfs(k)) cout<<"Yesn";
else cout<<"Non";
h.clear();
}
return 0;
}
