Skip to content

14181: 【原4181】填字游戏

题目

题目描述

author: 侯不会 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4181

Description

侯不会又遇到了一个不会的问题,现在他来请教你:
侯不会在玩一个填数游戏,这个游戏是在一个大小\(n\)行\(m\)列的矩阵上开展的,填数的规则如下
1.每行由自然数\(1~m\)填满,每行中每个数字用且只能用一次
2.相邻的自然数不会出现在相邻的方格中,包括左右相邻和上下相邻
3.第\(i\)列的得分为第\(i\)列所有自然数的总和\( * i\),总得分为\(m\)列得分之和
侯不会当然想拿最高分,所以请你告诉他填数的方案

Input Format

第一行,两个正整数\(n,m\)
接下来一个矩阵,矩阵的每一行为一个非负数,\(0\)表示需要填充,非\(0\)表示已经填充过且不能被更改。

Output Format

输出共一行,包含一个正整数,表示最大总分。

Sample Input

2 5  
1 3 0 2 0  
4 0 3 5 2

Sample Output

95

Data Range

对于100%的数据,\(3 <= n, m <= 7\), \(0\)的个数\(<=n * m\)。

Hint

数据保证至少存在一个解

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}

int n, m;
int lst[5041][7], tot;
bool ok[650][650] = {0};
int f[10][650];
void init(){
    n = read(), m = read();
    tot = 0;
    int tmp[10];
    REP(i, 0, m - 1)
        tmp[i] = i + 1;
    do{
        bool flag = true;
        REP(i, 1, m - 1){
            if (abs(tmp[i] - tmp[i - 1]) == 1){
                flag = false;
                break;
            }
        }
        if (flag){
            ++tot;
            REP(i, 0, m - 1)
                lst[tot][i] = tmp[i];
        }
    }while (next_permutation(tmp, tmp + m));
    REP(i, 1, tot)
        REP(j, i, tot){
            ok[i][j] = ok[j][i] = true;
            REP(k, 0, m - 1){
                if (abs(lst[i][k] - lst[j][k]) == 1){
                    ok[i][j] = ok[j][i] = false;
                    break;
                }
            }
        }
}
void solve(){
    int tmp[10], ans = 0;
    REP(i, 0, m - 1)
        tmp[i] = read();
    REP(i, 1, tot){
        bool flag = true;
        int res = 0;
        REP(j, 0, m - 1){
            if (tmp[j] != lst[i][j] && tmp[j]){
                flag = false;
                break;
            }
            res += lst[i][j] * (j + 1);
        }
        if (flag) f[1][i] = res;
        else f[1][i] = -1;
    }
    REP(i, 2, n){
        REP(j, 0, m - 1)
            tmp[j] = read();
        REP(j, 1, tot){
            f[i][j] = -1;
            REP(t, 1, tot){
                if (!ok[j][t] || f[i - 1][t] < 0) continue;
                bool flag = true;
                int res = 0;
                REP(u, 0, m - 1){
                    if (tmp[u] != lst[j][u] && tmp[u]){
                        flag = false;
                        break;
                    }
                    res += lst[j][u] * (u + 1);
                }
                if (flag) 
                    f[i][j] = max(f[i][j], f[i - 1][t] + res);
            }
            ans = max(ans, f[i][j]);
        }
    }
    printf("%d\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}