本人的写法与题解略有不同。
题解区的写法大都是将四个方向分开判断的。
我这里的写法是最套路的在一个 for 循环里循环四个方向判断。
感觉思路上没有问题,或者说我没发现问题
求助为什么过不去
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<ctime>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
const double d = 0.99996;
const double lim = 1e-15;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, m, c, ans, now_;
int p[55], cnt[55], top = 1;
int col[22][22], acol[22][22];
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
bool check(int x, int y) { return x < 1 || y < 1 || x > n || y > m; }
int Dev(int sx, int sy) {
int cnt = 0;
for(int i = 0; i < 4; ++i) {
int x = sx + dx[i], y = sy + dy[i]; // 找相邻的四个格子计算贡献
if(check(x, y) || check(sx, sy)) continue;
if(col[sx][sy] != col[x][y]) cnt++;
}
return cnt;
}
int calc(int sx, int sy, int ex, int ey) {
int res = 0;
// orz;
res = res - Dev(sx, sy) - Dev(ex, ey); // 减去原来的贡献
swap(col[sx][sy], col[ex][ey]);
res = res + Dev(sx, sy) + Dev(ex, ey); // 加上现在的贡献
return res;
}
void SA() {
// orz;
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) col[i][j] = acol[i][j];
double T = 50;
while(T > lim) {
int nowsx = rand() % n + 1;
int nowsy = rand() % m + 1;
int nowex = rand() % n + 1;
int nowey = rand() % m + 1;
// int pre = Calc();
// swap(col[nowsx][nowsy], col[nowex][nowey]); // 先交换
// int now = Calc();
int now = now_ + calc(nowsx, nowsy, nowex, nowey); // 再计算
int del = now - ans;
if(del < 0) { // 更新这个解
ans = now; now_ = now;
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) acol[i][j] = col[i][j];
} else if(exp(-del/T) > (double) rand() / RAND_MAX) {
now_ = now; // 一定概率接受当前这个状态
} else {
swap(col[nowsx][nowsy], col[nowex][nowey]); // 交换回去
}
T *= d;
}
}
void work() {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
ans += Dev(i, j);
}
}
// for(int i = 2; i <= n; ++i)
// for(int j = 1;j <= m; ++j)
// if(col[i][j] != col[i - 1][j]) ans++;
// for(int i = 1; i <= n; ++i)
// for(int j = 2;j <= m; ++j)
// if(col[i][j] != col[i][j - 1]) ans++;
ans /= 2;
now_ = ans;
// cout<<ans<<endl;
// for(int i = 1; i <= 30; ++i) SA();
while((double)clock() / CLOCKS_PER_SEC < 3.90) SA();//, cout<<ans<<endl;
}
int main()
{
srand(998244353);
n = read(), m = read(), c = read();
for(int i = 1; i <= c; ++i) p[i] = read();
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(cnt[top] == p[top]) ++top;
acol[i][j] = col[i][j] = top;
++cnt[top];
}
}
work();
// printf("%d\n", ans);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
printf("%d ", acol[i][j]);
}puts("");
}
return 0;
}