银河之星(记忆化搜索+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;}