瑟瑟发抖

3妹：2哥2哥，国家又降息啦，贷款市场报价利率（LPR）为：1年期LPR为3.45%，与前值持平；5年期以上LPR为3.95%，较前值下调25个基点。 你的房贷是不是可以又少了？
2哥 : 是啊，一个月能省还好几百呢。
3妹：省下来的钱用来干嘛，不如请我吃饭吧，嘿嘿。😁
2哥 : 也不是不可以，正好我也好久没吃大餐了，走，去搓一顿！
3妹：走着！话说2哥，你买的房子离你公司距离那么远，你准备去住吗？
2哥：暂时不住，近的我也买不起啊。工作可以换的嘛，哈哈
3妹：有道理。
2哥：说到房屋的距离，我今天看到一个关于“房屋的距离”的题目，让我们一起来做下吧~

吃瓜

题目：

给你三个 正整数 n 、x 和 y 。

在城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对所有 1 <= i < n ，都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。

对于每个 k（1 <= k <= n），你需要找出所有满足要求的 房屋对 [house1, house2] ，即从 house1 到 house2 需要经过的 最少 街道数为 k 。

返回一个下标从 1 开始且长度为 n 的数组 result ，其中 result[k] 表示所有满足要求的房屋对的数量，即从一个房屋到另一个房屋需要经过的 最少 街道数为 k 。

注意，x 与 y 可以 相等 。

示例 1：

image.png

输入：n = 3, x = 1, y = 3
输出：[6,0,0]
解释：让我们检视每个房屋对

• 对于房屋对 (1, 2)，可以直接从房屋 1 到房屋 2。
• 对于房屋对 (2, 1)，可以直接从房屋 2 到房屋 1。
• 对于房屋对 (1, 3)，可以直接从房屋 1 到房屋 3。
• 对于房屋对 (3, 1)，可以直接从房屋 3 到房屋 1。
• 对于房屋对 (2, 3)，可以直接从房屋 2 到房屋 3。

• 对于房屋对 (3, 2)，可以直接从房屋 3 到房屋 2。
  示例 2：

  
  image.png
  

  输入：n = 5, x = 2, y = 4
  输出：[10,8,2,0,0]
  解释：对于每个距离 k ，满足要求的房屋对如下：

• 对于 k == 1，满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), 以及 (5, 4)。
• 对于 k == 2，满足要求的房屋对有 (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), 以及 (5, 3)。
• 对于 k == 3，满足要求的房屋对有 (1, 5)，以及 (5, 1) 。

• 对于 k == 4 和 k == 5，不存在满足要求的房屋对。
  示例 3：

  
  image.png
  

  输入：n = 4, x = 1, y = 1
  输出：[6,4,2,0]
  解释：对于每个距离 k ，满足要求的房屋对如下：

• 对于 k == 1，满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), 以及 (4, 3)。
• 对于 k == 2，满足要求的房屋对有 (1, 3), (3, 1), (2, 4), 以及 (4, 2)。
• 对于 k == 3，满足要求的房屋对有 (1, 4), 以及 (4, 1)。
• 对于 k == 4，不存在满足要求的房屋对。

提示：

2 <= n <= 100
1 <= x, y <= n

思路：

思考

• 下标从 1 开始且长度为 n 的数组 result。所以先用下标从0开始的数组来求，最终再遍历一次把求得的结果放到 下标从1开始的result数组。
• result[k] 表示所有满足要求的房屋对的数量，即从一个房屋到另一个房屋需要经过的 最少 街道数为 k 。
• 路是双向的。
• 用佛洛依德算法求出多源最短路，再遍历多源最短路的结果，把权值放到下标从0开始的数组里。

java代码：

class Solution {
    public int[] countOfPairs(int n, int x, int y) {
        int w[][] = new int[n + 1][n + 1];
        int INF = Integer.MAX_VALUE / 2;
        
        //初始化 邻接矩阵。
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                w[i][j] = (i == j ? 0 : INF);

        //额外的捷径的权值是1。但不能是自身到自身，因为自身到自身的权值本来就是0.
        if (x != y) {
            w[x][y] = 1;
            w[y][x] = 1;
        }

        //建图，前后相邻 权值都是1。
        for (int i = 1; i < n; i++) {
            w[i][i + 1] = 1;
            w[i + 1][i] = 1;
        }

        //佛洛依德算法
        for (int p = 1; p <= n; p++)
            for (int st = 1; st <= n; st++)
                for (int end = 1; end <= n; end++)
                    w[st][end] = Math.min(w[st][end], w[st][p] + w[p][end]);

        //先用下标从0开始的数组来求结果。
        int[] res = new int[n + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (w[i][j] != INF)
                    res[w[i][j]]++;

        //最终再遍历一次把求得的结果放到 下标从1开始的result数组。
        int[] result  = new int[n];
        for (int i = 0; i < n; i++)
            result[i] = res[i + 1];

        return result;
    }
}