管道布线问题

问题描述

题目要求在一个由模块组成的办公大楼中，设计一种最便宜的管道布线方案。每个模块必须通过管道与恰好两个相邻模块相连，形成一个回路。给定楼层的布局和模块之间的管道铺设成本，目标是计算出最便宜的布线方案。

问题分析

1. 输入数据：

   • 每个楼层由一个二维网格表示，网格中的数字表示模块之间的管道铺设成本。
   • 每个模块可以与上下左右四个方向的模块相连。
   • 布局的外围由 # 表示，表示不可通行的区域。

2. 目标：

   • 找到一种布线方案，使得从服务模块出发，经过每个模块恰好一次，最后返回服务模块，且总成本最小。

3. 难点：

   • 需要处理复杂的网格结构。
   • 需要动态规划或图论算法来找到最优路径。

解题思路

1. 数据结构设计：

   • 使用二维数组 down 和 rgt 分别存储模块之间的上下和左右的管道铺设成本。
   • 使用 map<LL, int> 来存储状态和对应的最小成本，其中 LL 是状态的编码。

2. 状态编码与解码：

   • 使用一个长整型 LL 来编码当前的状态。状态包括每个模块的连接情况。
   • calc 函数用于将当前状态编码为一个长整型值。
   • decode 函数用于将长整型值解码为当前状态。

3. 动态规划：

   • 使用两个状态集合 f[0] 和 f[1]，分别表示当前状态和下一个状态。
   • 通过逐行逐列遍历模块，更新状态集合，计算每个状态的最小成本。
   • 在每一步中，根据当前模块的连接情况，更新状态集合。

4. 边界条件处理：

   • 确保在服务模块（左上角模块）处，状态的初始值为 0。
   • 确保在最后一个模块处，状态的最终值为 0，表示形成一个完整的回路。

代码实现

#include <iostream>
#include <stdio.h>
#include <vector>
#include <limits.h>
#include <string.h>
#include <map>
using namespace std;
typedef long long LL;
char p[30][30];
int down[10][10], rgt[10][10];
int n, m;
int a[11], x, y;
int b[8];
map<LL, int> f[2];

// 将当前状态编码为一个长整型值
inline LL calc()
{
    LL s = 0;
    int k = 0;
    for (int i = 0; i < 8; i++) b[i] = 0;
    for (int i = 0; i <= m; i++)
        if (a[i]) a[i] = b[a[i]] ? b[a[i]] : b[a[i]] = ++k;
    for (int i = m; i >= 0; i--) s <<= 3, s |= a[i];
    return s;
}

// 将长整型值解码为当前状态
inline void decode(LL t)
{
    for (int i = 0; i <= m; i++) a[i] = t & 7, t >>= 3;
}

// 更新状态集合
void push(map<LL, int> &f, LL x, int d)
{
    if (!f.count(x)) f[x] = INT_MAX;
    f[x] = min(f[x], d);
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        // 使用 fgets 替代 gets
        fgets(p[0], sizeof(p[0]), stdin);
        for (int i = 0; i < 2 * n + 1; i++)
            fgets(p[i], sizeof(p[i]), stdin);

        // 提取上下和左右的管道成本
        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < m; j++)
                down[i][j] = p[2 * i + 2][2 * j + 1] - '0';
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m - 1; j++)
                rgt[i][j] = p[2 * i + 1][2 * j + 2] - '0';

        int cur = 0, nxt = 1;
        f[cur].clear();
        f[cur][0] = 0; // 初始状态
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                f[nxt].clear();
                for (map<LL, int>::iterator it = f[cur].begin(); it != f[cur].end(); it++)
                {
                    decode(it->first);
                    int d;
                    if (j == 1 && a[0] != 0) continue; // 服务模块必须从 0 开始
                    x = a[0], y = a[j];
                    if (!x && !y)
                    {
                        a[0] = a[j] = 7; // 新的连接
                        push(f[nxt], calc(), it->second);
                    }
                    else if (x && y)
                    {
                        d = it->second;
                        d += rgt[i - 1][j - 2] + down[i - 2][j - 1]; // 更新成本
                        if (x == y && (i != n || j != m)) continue; // 避免形成环
                        for (int k = 0; k <= m; k++)
                            if (a[k] == x) a[k] = y; // 合并连接
                        a[0] = a[j] = 0; // 清除连接
                        push(f[nxt], calc(), d);
                    }
                    else if (x && !y)
                    {
                        d = it->second + rgt[i - 1][j - 2]; // 向右连接
                        push(f[nxt], calc(), d);
                        a[0] = 0, a[j] = x; // 更新连接
                        push(f[nxt], calc(), d);
                    }
                    else
                    {
                        d = it->second + down[i - 2][j - 1]; // 向下连接
                        push(f[nxt], calc(), d);
                        a[j] = 0, a[0] = y; // 更新连接
                        push(f[nxt], calc(), d);
                    }
                }
                cur ^= 1, nxt ^= 1; // 交换状态集合
            }
        printf("%d\n", f[cur][0]); // 输出最小成本
    }
    return 0;
}

代码解析

1. 输入处理：

   • 使用 fgets 读取楼层的 ASCII 描述。
   • 提取模块之间的上下和左右的管道成本，存储在 down 和 rgt 数组中。

2. 状态编码与解码：

   • calc 函数将当前状态编码为一个长整型值，方便存储和比较。
   • decode 函数将长整型值解码为当前状态，用于动态规划的更新。

3. 动态规划：

   • 使用两个状态集合 f[0] 和 f[1]，分别表示当前状态和下一个状态。
   • 通过逐行逐列遍历模块，更新状态集合，计算每个状态的最小成本。
   • 在每一步中，根据当前模块的连接情况，更新状态集合。

4. 输出结果：

   • 最终输出最小成本，即从服务模块出发，经过每个模块恰好一次，最后返回服务模块的最小总成本。

总结

本题是一个典型的动态规划问题，需要设计合适的状态编码和解码方法，并通过动态规划逐步更新状态集合，最终找到最优解。通过上述代码实现，可以高效地解决管道布线问题。