题目跳转

HDOJ5113

题目大意

n*m的棋盘，用k种颜色（每种颜色可以染Ci次）染完，且没有十字相邻格子的颜色一致。

思路

DFS剪枝

当一种颜色超过剩余未染的格子的一半，没有结果。（可以用二色的情况类比）
这个一半建议代入数据实操看看。

这道题格式错了报WA的。让我好是疑惑。。

数据生成器

自己写来对拍用的，不保证没问题。

#include <bits/stdc++.h>
#include <ctime>

using namespace std;

typedef long long LL;

int k, sum;
int a[30];

int random(int x)
{ // 获取 0~x-1 中间的一个随机数
  if (!x)
    return 0;
  return (LL)rand() * rand() % x;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  srand(time(0));
  cout << 5000 << endl;
  for (int T = 0; T < 5000; T++)
  {
    int n = random(5) + 1, m = random(5) + 1;
    sum = n * m;
    k = random(sum) + 1;
    cout << n << ' ' << m << ' ' << k << endl;
    for (int i = 0; i < k; i++)
      a[i] = 1;
    sum -= k;
    for (int i = 0; i < sum; i++)
      a[random(k)]++;
    for (int i = 0; i < k; i++)
      cout << a[i] << ' ';
    cout << endl;
  }
  return 0;
}

CODE

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 6;

int n, m, k;
int dxy[4][2] = {
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0},
};
int g[N][N], ans[N][N], color_cnt[30];
bool flag;

bool check(int x, int y)
{
  for (int i = 0; i < 4; i++)
  {
    int a = x + dxy[i][0], b = y + dxy[i][1];
    if (a < 0 || a >= n || b < 0 || b >= m)
      continue;
    if (g[x][y] == g[a][b])
      return false;
  }
  return true;
}
bool dfs(int x, int y, int type, int cnt)
{
  g[x][y] = type;
  color_cnt[type]--;
  if (!check(x, y))
  {
    g[x][y] = 0;
    color_cnt[type]++;
    return false;
  }
  for (int i = 1; i <= k; i++)
  {
    if (color_cnt[i] * 2 - 1 > n * m - cnt)
    {
      g[x][y] = 0;
      color_cnt[type]++;
      return false;
    }
  }
  // for (int i = 0; i < n; i++)
  // {
  //   for (int j = 0; j < m; j++)
  //     cout << g[i][j] << ' ';
  //   cout << endl;
  // }
  // cout << endl;
  if (cnt == n * m)
  {
    memcpy(ans, g, sizeof g);
    g[x][y] = 0;
    color_cnt[type]++;
    return true;
  }
  // 也可以改成从左上搜到右下，即a = x,b = y+1; a += b/m,b %= m;
  for (int i = 0; i < 4; i++) 
  {
    int a = x + dxy[i][0], b = y + dxy[i][1];
    if (a < 0 || a >= n || b < 0 || b >= m || g[a][b])
      continue;
    for (int j = 1; j <= k; j++)
    {
      if (color_cnt[j])
      {
        if (dfs(a, b, j, cnt + 1))
        {
          g[x][y] = 0;
          color_cnt[type]++;
          return true;
        }
      }
    }
  }
  g[x][y] = 0;
  color_cnt[type]++;
  return false;
}

int main()
{
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  scanf("%d", &T);
  for (int CC = 1; CC <= T; CC++)
  {
    flag = false;
    scanf("%d%d%d", &n, &m, &k);
    int maxv = -1;
    for (int i = 1; i <= k; i++)
    {
      scanf("%d", &color_cnt[i]);
      if (color_cnt[i] > maxv)
        maxv = color_cnt[i];
    }
    if (maxv * 2 - 1 > n * m)
    {
      printf("Case #%d:\nNO\n", CC);
      continue;
    }

    printf("Case #%d:\n", CC);
    for (int i = 1; i <= k; i++)
      if (dfs(0, 0, i, 1))
      {
        puts("YES");
        for (int a = 0; a < n; a++)
        {
          printf("%d", ans[a][0]);
          for (int b = 1; b < m; b++)
            printf(" %d", ans[a][b]);
          puts("");
        }
        flag = true;
        break;
      }
    if (!flag)
      puts("NO");
  }
  return 0;
}