> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/math/296.-best-meeting-point.md).

# 296. Best Meeting Point

给定由0和1组成的二维矩阵，在矩阵里找一个位置使得它离所有的1的曼哈顿距离（distance(p1, p2) = `|p2.x - p1.x| + |p2.y - p1.y|`）最小。这道题相当于在找针对曼哈顿距离的Geometric median。根据曼哈顿距离的定义，x和y可以分开找各自的最小，最后再相加。对于一维的A，B两点，当落在A和B内任意位置的曼哈顿距离和都一样，且都小于落在AB外的任意点。当拓展到更多点时，比如ABCD，同理落在BC间距离和都一样，且小于落在BC外。因此首尾两个指针同时往中心移动并累加它俩之间的距离就是一个维度的答案。对另一个纬度同理，最后两个纬度解相加是全局解。

题目和解法参考自[这](https://link.zhihu.com/?target=https%3A//www.cnblogs.com/grandyang/p/5291058.html)。

```cpp
class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        const int M = grid.size(), N = M == 0 ? 0 : grid[0].size();
        vector<int> rows, cols;
        int res = 0;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] != 1) continue;
                rows.push_back(i);
                cols.push_back(j);
            }
        }
        sort(cols.begin(), cols.end());
        while (i < j) res += rows[j] - rows[i] + cols[j--] - cols[i++];
        return res;
    }
};

```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/math/296.-best-meeting-point.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.