C++有一个由 0 和 1 组成的 n 行 n 列的数字方阵，其中只有一个 1，其余都是 0。现在我们想通过一些操作把 1 换到数字方阵的左上角。每次操作我们可以交换方阵中的任意两行或者任意两列，请问为了完成目标，我们最少需要交换多少次？ 输入格式 第一行，一个整数 n。 接下来 n 行，每行 n 个数，表示数字方阵。 输出格式 一行一个整数，表示答案。 样例输入 4 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 样例输出 1

这是一个经典的问题，可以使用贪心算法求解。我们可以考虑每次交换时将距离左上角最近的 1 移到左上角，然后再将距离左上角次近的 1 移到左上角，以此类推，最终可以将 1 移到左上角。

具体来说，我们可以先找到数字方阵中 1 所在的行和列，分别记为 $r$ 和 $c$。然后我们可以将第 $r$ 行和第 1 行进行交换，将第 $c$ 列和第 1 列进行交换，这样 1 就被移动到了左上角。接下来，我们可以将距离左上角最近的 1 进行类似的操作，每次操作可以将某行或某列上的 1 移动到左上角。

具体实现时，我们可以维护一个距离左上角最近的 1，每次找到距离最近的 1 进行交换即可。可以使用一个优先队列来维护距离最近的 1，每次找到距离最近的 1 进行交换后，更新优先队列中的元素。

代码如下：

相关问题

帮我用C++写C++有一个由 0 和 1 组成的 n 行 n 列的数字方阵，其中只有一个 1，其余都是 0。现在我们想通过一些操作把 1 换到数字方阵的左上角。每次操作我们可以交换方阵中的任意两行或者任意两列，请问为了完成目标，我们最少需要交换多少次？ 输入格式 第一行，一个整数 n。 接下来 n 行，每行 n 个数，表示数字方阵。 输出格式 一行一个整数，表示答案。

好的，下面是代码实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 105;
int n;
int a[N][N];
bool vis[N][N];

struct Node {
    int x, y, dis;
    Node(int _x, int _y, int _dis): x(_x), y(_y), dis(_dis) {}
    bool operator< (const Node& t) const {
        return dis > t.dis;
    }
};

int main() {
    cin >> n;
    int x, y;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            if (a[i][j] == 1) {
                x = i, y = j;
            }
        }
    }

    priority_queue<Node> q;
    q.push(Node(x, y, 0));
    vis[x][y] = true;

    int ans = 0;
    while (!q.empty()) {
        auto t = q.top();
        q.pop();
        if (t.x == 1 && t.y == 1) {
            ans = t.dis;
            break;
        }
        if (t.x != 1) {
            int k = t.x;
            for (int i = 1; i <= n; i++) {
                if (i != t.x && !vis[i][t.y]) {
                    vis[i][t.y] = true;
                    q.push(Node(i, t.y, t.dis + abs(i - k)));
                }
            }
        }
        if (t.y != 1) {
            int k = t.y;
            for (int i = 1; i <= n; i++) {
                if (i != t.y && !vis[t.x][i]) {
                    vis[t.x][i] = true;
                    q.push(Node(t.x, i, t.dis + abs(i - k)));
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}

具体思路和上面所说的一样，使用了一个优先队列来维护距离最近的 1，每次找到距离最近的 1 进行交换后，更新优先队列中的元素。时间复杂度为 $O(n^2\log n)$。

C++实现 输入一个整数n，输出2n-1行的由*组成的菱形

下面是使用C++语言实现输入一个整数n，输出2n-1行的由*组成的菱形的代码：

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入一个整数n：";
    cin >> n;
    for (int i = 1; i <= n; i++) { // 输出上半部分
        for (int j = 1; j <= n-i; j++) {
            cout << ' ';
        }
        for (int j = 1; j <= 2*i-1; j++) {
            cout << '*';
        }
        cout << endl;
    }
    for (int i = n-1; i >= 1; i--) { // 输出下半部分
        for (int j = 1; j <= n-i; j++) {
            cout << ' ';
        }
        for (int j = 1; j <= 2*i-1; j++) {
            cout << '*';
        }
        cout << endl;
    }
    return 0;
}

运行示例：

请输入一个整数n：4
   *
  ***
 *****
*******
 *****
  ***
   *