银河之星(记忆化搜索+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=(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<<"Yes\n";
    else cout<<"No\n";
    h.clear();
  }  
  return 0;
}