城市街道涂色问题题解

问题描述

我们需要计算市长可能经过的所有最短路径上的街道块数量。给定城市网格的街道方向（东-西和南-北）以及市长可能访问的地点列表，要求找出所有这些地点之间最短路径上街道块的总数。

解题思路

1. 构建城市网格图：根据输入的街道方向信息构建城市网格的邻接关系
2. 计算所有点对之间的最短路径：使用广度优先搜索(BFS)或Floyd-Warshall算法
3. 统计所有最短路径上的边：记录所有可能出现在最短路径上的街道块
4. 去重计数：确保每条街道块只被计算一次

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <climits>
using namespace std;

struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) {}
    bool operator<(const Point& other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
};

struct Edge {
    Point from, to;
    Edge(Point f, Point t) : from(f), to(t) {}
    bool operator<(const Edge& other) const {
        if (from.x != other.from.x) return from.x < other.from.x;
        if (from.y != other.from.y) return from.y < other.from.y;
        if (to.x != other.to.x) return to.x < other.to.x;
        return to.y < other.to.y;
    }
};

void solve() {
    string ew, ns;
    cin >> ew >> ns;
    int rows = ns.size() + 1;
    int cols = ew.size() + 1;
    
    // 构建邻接表
    vector<vector<vector<Point>>> adj(rows, vector<vector<Point>>(cols));
    
    // 处理东西向街道
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols - 1; ++j) {
            char dir = ew[j];
            if (dir == 'E' || dir == 'T') {
                adj[i][j].push_back(Point(i, j+1));
            }
            if (dir == 'W' || dir == 'T') {
                adj[i][j+1].push_back(Point(i, j));
            }
        }
    }
    
    // 处理南北向街道
    for (int i = 0; i < rows - 1; ++i) {
        for (int j = 0; j < cols; ++j) {
            char dir = ns[i];
            if (dir == 'S' || dir == 'T') {
                adj[i][j].push_back(Point(i+1, j));
            }
            if (dir == 'N' || dir == 'T') {
                adj[i+1][j].push_back(Point(i, j));
            }
        }
    }
    
    int n;
    cin >> n;
    vector<Point> points;
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        points.emplace_back(x, y);
    }
    
    set<Edge> painted_edges;
    
    // 计算所有点对之间的最短路径
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            Point start = points[i];
            Point end = points[j];
            
            // BFS计算最短路径
            vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
            vector<vector<Point>> prev(rows, vector<Point>(cols, Point(-1, -1)));
            queue<Point> q;
            
            dist[start.x][start.y] = 0;
            q.push(start);
            
            while (!q.empty()) {
                Point current = q.front();
                q.pop();
                
                if (current.x == end.x && current.y == end.y) {
                    break;
                }
                
                for (Point neighbor : adj[current.x][current.y]) {
                    if (dist[neighbor.x][neighbor.y] == INT_MAX) {
                        dist[neighbor.x][neighbor.y] = dist[current.x][current.y] + 1;
                        prev[neighbor.x][neighbor.y] = current;
                        q.push(neighbor);
                    }
                }
            }
            
            // 回溯路径并记录边
            Point current = end;
            while (prev[current.x][current.y].x != -1) {
                Point p = prev[current.x][current.y];
                painted_edges.insert(Edge(min(p, current), max(p, current)));
                current = p;
            }
        }
    }
    
    cout << painted_edges.size() << " street blocks need to be painted.\n\n";
}

int main() {
    int t;
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        cout << "Case #" << i << ":\n";
        solve();
    }
    return 0;
}

关键点解析

1. 城市网格建模：

   • 使用邻接表表示街道连接关系
   • 根据输入的'E'、'W'、'N'、'S'、'T'确定街道方向

2. 最短路径计算：

   • 使用BFS算法计算两点之间的最短路径
   • 记录路径上的所有边

3. 边去重处理：

   • 使用集合(set)存储所有可能出现在最短路径上的边
   • 确保每条边只被计算一次

4. 输入输出处理：

   • 正确处理多测试用例
   • 按照要求格式输出结果

复杂度分析

• 时间复杂度：O(T × N² × R×C)，其中T是测试用例数，N是地点数，R和C是网格行列数
• 空间复杂度：O(R×C)，用于存储距离和前置节点信息

该解决方案有效地解决了市长可能经过的所有最短路径上的街道块计数问题，通过BFS确保找到最短路径，并使用集合去重确保准确计数。