排序從 0 到 n ^ 2 – 1 的數字矩陣的最低成本 · GeeksForGeeks 中文系列教程

# 排序從 0 到 n ^ 2 – 1 的數字矩陣的最低成本 > 原文： [https://www.geeksforgeeks.org/minimum-cost-sort-matrix-numbers-0-n2-1/](https://www.geeksforgeeks.org/minimum-cost-sort-matrix-numbers-0-n2-1/) 給定一個 n x n 矩陣，其中包含 0 到 n <sup>2</sup> -1 范圍內的所有數字。問題是要計算以嚴格遞增的順序重新排列矩陣中所有數字所需的總能量，即，重新排列后，第一行包含從 0 到 n-1 的'n'個數字，然后第二行包含從 n 到 2n- 1，依此類推，直到最后一行或第 n 行。可以從當前位置向左，向右，頂部或底部四個方向移動數字，以在最終修改的矩陣中到達目標。將號碼從當前位置轉移到所需目的地的步數是號碼移動所需的能量。例如，在 4 x 4 矩陣中，數字“ 6”出現在位置（2，3）。它在修改后的矩陣中的目標位置是（1，1）。因此，“ 6”向左移動 2 步，向上移動 1 步到達位置（1，1）。共移動了 3 步，因此“ 6”所需的能量為 3 個單位。這樣，我們必須總結所有數字的移動/重新排列所需的所有能量。 **示例**： ``` Input : mat[][] = { {3, 0}, {2, 1} } Output : 4 units For number '3': Move it one step right and one step down. Total 2 steps thus energy required = 2 units. For number '0': Move it one step left. Total 1 step thus energy required = 1 unit. For number '1': Move it one step up. Total 1 step thus energy required = 1 unit. Total energy required = 4 units. Input : mat[][] = { {4, 7, 10, 3}, {8, 5, 6, 1}, {9, 11, 10, 2}, {15, 13, 14, 12} } Output : 22 units ``` **算法**： ``` calculateEnergy(mat, n) Declare i_des, j_des, q Initialize tot_energy = 0 for i = 0 to n-1 for j = 0 to n-1 q = mat[i][j] / n i_des = q j_des = mat[i][j] - (n * q) tot_energy += abs(i_des - i) + abs(j_des - j) return tot_energy ``` ## C++ ```cpp // C++ implementation to find the total energy // required to rearrange the numbers #include <bits/stdc++.h> using namespace std; #define SIZE 100 // function to find the total energy // required to rearrange the numbers int calculateEnergy(int mat[SIZE][SIZE], int n) { ????int i_des, j_des, q; ????int tot_energy = 0; ????// nested loops to access the elements ????// of the given matrix ????for (int i = 0; i < n; i++) { ????????for (int j = 0; j < n; j++) { ????????????// store quotient ????????????q = mat[i][j] / n; ????????????// final destination location (i_des, j_des) of ????????????// the element mat[i][j] is being calculated ????????????i_des = q; ????????????j_des = mat[i][j] - (n * q); ????????????// energy required for the movement of the ????????????// element mat[i][j] is calculated and then ????????????// accumulated in the 'tot_energy' ????????????tot_energy += abs(i_des - i) + abs(j_des - j); ????????} ????} ????// required total energy ????return tot_energy; } // Driver program to test above int main() { ????int mat[SIZE][SIZE] = { { 4, 7, 0, 3 }, ????????????????????????????{ 8, 5, 6, 1 }, ????????????????????????????{ 9, 11, 10, 2 }, ????????????????????????????{ 15, 13, 14, 12 } }; ????int n = 4; ????cout << "Total energy required = " ?????????<< calculateEnergy(mat, n) << " units"; ????return 0; } ``` ## Java ```java // Java implementation to find // the total energy required? // to rearrange the numbers import java.util.*; import java.lang.*; public class GfG{ ????private final static int SIZE? = 100; ????// function to find the total energy ????// required to rearrange the numbers ????public static int calculateEnergy(int mat[][], ????int n) ????{ ????????int i_des, j_des, q; ????????int tot_energy = 0; ????????// nested loops to access the elements ????????// of the given matrix ????????for (int i = 0; i < n; i++) { ????????????for (int j = 0; j < n; j++) { ????????????????// store quotient ????????????????q = mat[i][j] / n; ????????????????// final destination location ????????????????// (i_des, j_des) of ????????????????// the element mat[i][j] is ????????????????// being calculated ????????????????i_des = q; ????????????????j_des = mat[i][j] - (n * q); ????????????????// energy required for the ????????????????// movement of the ????????????????// element mat[i][j] is ????????????????// calculated and then ????????????????// accumulated in the 'tot_energy' ????????????????tot_energy += Math.abs(i_des - i) + ????????????????Math.abs(j_des - j); ????????????} ????????} ????????// required total energy ????????return tot_energy; ????} ????// Driver function ????public static void main(String argc[]){ ????????int[][] mat = new int[][] {{ 4, 7, 0, 3 }, ???????????????????????????????????{ 8, 5, 6, 1 }, ???????????????????????????????????{ 9, 11, 10, 2 }, ???????????????????????????????????{ 15, 13, 14, 12 }}; ????????int n = 4; ????System.out.println("Total energy required = " ?????????+ calculateEnergy(mat, n) + " units"); ????} } // This code is contributed by Sagar Shukla? ``` ## Python3 ```py # implementation to find the total # energy required to rearrange the # numbers n = 4 # function to find the total energy # required to rearrange the numbers def calculateEnergy(mat,n): ????tot_energy = 0 ????# nested loops to access the? ????# elements of the given matrix ????for i in range(n): ????????for j in range(n): ????????????#store quotient ????????????q = mat[i][j]//n ????????????# final destination location ????????????# (i_des, j_des) of the? ????????????# element mat[i][j] is being ????????????# calculated ????????????i_des = q ????????????j_des = mat[i][j]- (n*q) ????????????# energy required for the ????????????# movement of the element ????????????# mat[i][j] is calculated? ????????????# and then accumulated in ????????????# the 'tot_energy' ????????????tot_energy += (abs(i_des-i)? ?????????????????????????+ abs(j_des-j)) ????# required total energy ????return tot_energy # Driver Program mat = [[4, 7, 0, 3], ???????[8, 5, 6, 1], ?????????[9, 11, 10, 2], ???????[15, 13, 14, 12]] print("Total energy required = ", ????????calculateEnergy(mat,n), "units") # This code is contributed by Shrikant13\. ``` ## C# ```cs // C# implementation to find // the total energy required // to rearrange the numbers using System; class GFG { ????// function to find the total energy ????// required to rearrange the numbers ????public static int calculateEnergy(int[, ] mat, ????????????????????????????????????????????int n) ????{ ????????int i_des, j_des, q; ????????int tot_energy = 0; ????????// nested loops to access the elements ????????// of the given matrix ????????for (int i = 0; i < n; i++) { ????????????for (int j = 0; j < n; j++) { ????????????????// store quotient ????????????????q = mat[i, j] / n; ????????????????// final destination location ????????????????// (i_des, j_des) of ????????????????// the element mat[i][j] is ????????????????// being calculated ????????????????i_des = q; ????????????????j_des = mat[i, j] - (n * q); ????????????????// energy required for the ????????????????// movement of the ????????????????// element mat[i][j] is ????????????????// calculated and then ????????????????// accumulated in the 'tot_energy' ????????????????tot_energy += Math.Abs(i_des - i) +? ??????????????????????????????Math.Abs(j_des - j); ????????????} ????????} ????????// required total energy ????????return tot_energy; ????} ????// Driver function ????public static void Main() ????{ ????????int[, ] mat = new int[, ]{ { 4, 7, 0, 3 }, ???????????????????????????????????{ 8, 5, 6, 1 }, ???????????????????????????????????{ 9, 11, 10, 2 }, ???????????????????????????????????{ 15, 13, 14, 12 } }; ????????int n = 4; ????????Console.Write("Total energy required = " +? ??????????????calculateEnergy(mat, n) + " units"); ????} } // This code is contributed by Sam007 ``` ## PHP ```php <?php // PHP implementation to find? // the total energy required? // to rearrange the numbers // function to find the total energy // required to rearrange the numbers function calculateEnergy($mat, $n) { ????$i_des; $j_des; $q; ????$tot_energy = 0; ????// nested loops to access the? ????// elements of the given matrix ????for ($i = 0; $i < $n; $i++)? ????{ ????????for ($j = 0; $j < $n; $j++)? ????????{ ????????????// store quotient ????????????$q = (int)($mat[$i][$j] / $n); ????????????// final destination location? ????????????// (i_des, j_des) of the element ????????????// mat[i][j] is being calculated ????????????$i_des = $q; ????????????$j_des = $mat[$i][$j] - ($n * $q); ????????????// energy required for the movement? ????????????// of the element mat[i][j] is? ????????????// calculated and then accumulated? ????????????// in the 'tot_energy' ????????????$tot_energy += abs($i_des - $i) +? ???????????????????????????abs($j_des - $j); ????????} ????} ????// required total energy ????return $tot_energy; } // Driver Code $mat = array(array (4, 7, 0, 3), ?????????????array (8, 5, 6, 1), ?????????????array (9, 11, 10, 2), ?????????????array (15, 13, 14, 12)); $n = 4; echo "Total energy required = ", calculateEnergy($mat, $n) , " units"; // This code is contributed by ajit ?> ``` **輸出**： ``` Total energy required = 22 units ``` **時間復雜度**： `O(n^2)` 本文由 [**Ayush Jauhari**](https://auth.geeksforgeeks.org/profile.php?user=ayushjauhari14) 貢獻。如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。