裸退火,每次交换两个格子即可。依旧不会调参,稍微抄了点参数并且把随机种子设成了一个神奇的数字终于过掉了。
#include#include #include #include #include #include #include using namespace std;#define ll long long#define N 22#define M 55#define T0 1#define T1 1E-14#define delta 0.9999char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,c,a[M],color[N][N],cnt,ans,goal[N][N];int wx[4]={ 1,0,0,-1},wy[4]={ 0,1,-1,0};int calc(int x,int y){ int t=0; for (int k=0;k<4;k++) if (x+wx[k]>=1&&x+wx[k]<=n&&y+wy[k]>=1&&y+wy[k]<=m) if (color[x][y]!=color[x+wx[k]][y+wy[k]]) t++; return t;}void anneal(){ double T=T0; while (T>T1) { int x1=rand()%n+1,y1=rand()%m+1,x2=rand()%n+1,y2=rand()%m+1; while (x1==x2||y1==y2) x1=rand()%n+1,y1=rand()%m+1,x2=rand()%n+1,y2=rand()%m+1; int d=0; d-=calc(x1,y1),d-=calc(x2,y2); swap(color[x1][y1],color[x2][y2]); d+=calc(x1,y1),d+=calc(x2,y2); if (d<0||rand() m) x++,y=1; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=0;k<4;k++) if (i+wx[k]>=1&&i+wx[k]<=n&&j+wy[k]>=1&&j+wy[k]<=m) if (color[i][j]!=color[i+wx[k]][j+wy[k]]) cnt++; ans=cnt>>=1; memcpy(goal,color,sizeof(color)); for (int i=1;i<=20;i++) anneal(); for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) cout< <<' '; cout<