We define a magic square to be an nXn matrix of distinct positive integers from 1 to n^2 where the sum of any row, column, or diagonal of length n is always equal to the same number: the magic constant.
You will be given a 3X3 matrix s of integers in the inclusive range [1,9]. We can convert any digit a to any other digit b in the range [1,9] at cost of abs(a-b). Given s, convert it into a magic square at a minimal cost. Find this cost.
Note: The resulting magic square must contain distinct integers in the inclusive range [1,9].
You will be given a 3X3 matrix s of integers in the inclusive range [1,9]. We can convert any digit a to any other digit b in the range [1,9] at cost of abs(a-b). Given s, convert it into a magic square at a minimal cost. Find this cost.
Note: The resulting magic square must contain distinct integers in the inclusive range [1,9].
Example:
Input: brr[3][3]={{5,3,4},{1,5,8},{6,4,2}}
Output: 7
Approach
C++
#include <bits/stdc++.h>using namespace std;int main(){int brr[3][3] = {{5, 3, 4}, {1, 5, 8}, {6, 4, 2}};int arr[8][3][3] = {{{8, 1, 6}, {3, 5, 7}, {4, 9, 2}},{{6, 1, 8}, {7, 5, 3}, {2, 9, 4}},{{4, 9, 2}, {3, 5, 7}, {8, 1, 6}},{{2, 9, 4}, {7, 5, 3}, {6, 1, 8}},{{8, 3, 4}, {1, 5, 9}, {6, 7, 2}},{{4, 3, 8}, {9, 5, 1}, {2, 7, 6}},{{6, 7, 2}, {1, 5, 9}, {8, 3, 4}},{{2, 7, 6}, {9, 5, 1}, {4, 3, 8}}};int res = INT_MAX;for (int k = 0; k < 8; k++){int ans = 0;for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++)ans += abs(arr[k][i][j] - brr[i][j]);}res = min(res, ans);}cout << res << "\n";return 0;}
No comments:
Post a Comment