Computer >> Máy Tính >  >> Lập trình >> C ++

Đếm hình vuông ma thuật trong một lưới trong C ++

Chúng ta được đưa ra với một ma trận các số. Mục đích là để tìm số hình vuông Phép thuật hiện diện bên trong ma trận đã cho.

Hình vuông ma thuật, nếu được coi là ma trận, là ma trận 3X3 chứa các phần tử từ 1 đến 9 giống như lưới trong Sudoku. Thuộc tính là -

  • Tất cả các con số đều xảy ra đúng một lần.
  • Tổng của tất cả 9 ô trong ma trận là 45.
  • Tổng của mỗi hàng 3 là 15.
  • Tổng của mỗi cột 3 là 15.
  • Tổng các đường chéo của 3 là 5.
  • Để có các tổng như vậy, 5 luôn nằm ở giữa cả hai đường chéo.

Đầu vào 

int arr[][]= { { 1,2,3,0 }, { 4,5,6,1 }, { 7,8,9,0 } };

Đầu ra 

Magic Squares present: 0

Giải thích - Lập ma trận dạng để hiểu -

1 2 3 0
4 5 6 1
7 8 9 0

Tất cả các phần tử nằm trong khoảng từ 1 đến 9 và là duy nhất. Nhưng,

1 + 2 + 3 =6! =4 + 5 + 6 =15! =7 + 8 + 9 =23

Ngoài ra, tổng các đường chéo không bằng 15.

Đầu vào 

arr[][]= { { 1,2,3,0 }, { 4,5,6,1 }, { 7,8,9,0 } };

Đầu ra 

Magic Squares present : 1

Giải thích - Lập ma trận dạng để hiểu -

1 6 8 4
8 1 6 0
3 5 7 1
4 9 2 0

Tất cả các số là duy nhất và trong phạm vi từ 1 đến 9.

Tổng các hàng, 8 + 1 + 6 =3 + 5 + 7 =4 + 9 + 2 =15

Tổng các cột, 8 + 3 + 4 =1 + 5 + 9 =6 + 7 + 2 =15

Tổng các đường chéo, 8 + 5 + 2 =4 + 5 + 6 =15

Ngoài ra, thêm 1 đến 9, chúng ta nhận được 45 và 5 là giữa cả hai đường chéo.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

  • Mảng số nguyên Grid [] [] lưu trữ số, hàng và col lưu trữ kích thước của nó.

  • Hàm magicSquare (int a, int b… ..int i) nhận tất cả 9 phần tử làm đầu vào và kiểm tra xem nó có phải là hình vuông ma thuật hay không. Trả về 1 nếu nó là hình vuông ma thuật, trả về 1 nếu không.

  • Ở đây chúng ta sẽ lấy mảng arr [9] để lưu trữ tất cả các tham số và kiểm tra xem chúng có phải là duy nhất hay không bằng cách kiểm tra xem chúng có chiếm các ô duy nhất trong đó không. Nếu một ô có số đếm <1 có nghĩa là không. không nằm trong phạm vi từ 1 đến 9, hoặc nếu đếm> 1 thì không. không phải là duy nhất. đặt cờ =0

  • Nếu cờ là 1 thì chúng tôi sẽ kiểm tra tổng của hàng, cột, đường chéo là 15. Nếu đúng thì đó là hình vuông amagic. Trả về 1 khác trả về 0.

  • Hàm countSquares (int G [3] [4], int R, int C) nhận một lưới, các hàng và cột của nó làm đầu vào và đếm số không. hình vuông kỳ diệu hiện diện trong đó.

  • Số đếm được sử dụng để lưu trữ số lượng các ô vuông như vậy.

  • Bắt đầu đi ngang từ phần tử đầu tiên cho đến hàng-2, col-2 (ma trận 3X3)

  • Nếu giữa đường chéo G [i + 1] [j + 1] không phải là 5 thì không thể có hình vuông ma thuật, hãy bỏ qua phép lặp hiện tại.

  • Kiểm tra tất cả 9 phần tử khác bằng cách chuyển nó cho magicSquare (int a to i)

  • Tất cả 9 phần tử bao gồm G [i] [j] là G [i + 1] [j], G [i + 2] [j], G [i + 1] [j + 1], G [i] [j +1], G [i] [j + 2], G [i + 2] [j + 2], G [i + 2] [j + 1], G [i + 1] [j + 2]

  • Nếu nó trả về 1 số tăng.

  • Cuối cùng, kết quả trả về là kết quả mong muốn.

Ví dụ 

#include <bits/stdc++.h>
using namespace std;
// to check is subgrid is Magic Square
int magicSquare(int a, int b, int c, int d, int e,
int f, int g, int h, int i){
   int flag=1; // to mark all numbers are unique and between 1 to 9
   int arr[9]={0};
   arr[a-1]++;
   arr[b-1]++;
   arr[c-1]++;
   arr[d-1]++;
   arr[e-1]++;
   arr[f-1]++;
   arr[g-1]++;
   arr[h-1]++;
   arr[i-1]++;
   for(int i=0;i<9;i++)
      if(arr[i]>1 || arr[i]<1) //every number occurs exactly once{
         flag=0;
         break;
   }
   // checking all sums as 15
   if (flag==1 && (a + b + c) == 15 && (d + e + f) == 15 && (g + h + i) == 15 && (a + d + g) == 15 &&(b + e + h) == 15 && (c + f + i) == 15 &&(a + e + i) == 15 && (c + e + g) == 15)
   return 1;
   return 0;
}
int countSquares(int G[3][4],int R, int C){
   int count = 0;
   for (int i = 0; i < R - 2; i++)
      for (int j = 0; j < C - 2; j++) {
         if (G[i + 1][j + 1] != 5)
            continue;
      int ismagic=magicSquare(G[i][j], G[i][j + 1], G[i][j + 2], G[i + 1][j], G[i + 1][j + 1],
      G[i + 1][j + 2], G[i + 2][j], G[i + 2][j + 1], G[i + 2][j + 2]);
      // check for magic square subgrid
      if (ismagic==1)
         count++;
      }
      return count;
}
int main(){
   int Grid[3][4] = { { 4, 3, 8, 4 },{ 9, 5, 1, 9 },{ 2, 7, 6, 2 } };
   int row=3;
   int col=4;
   cout <<"Count of Magic Squares in Grid: "<<countSquares(Grid,row,col);
   return 0;
}

Đầu ra 

Count of Magic Squares in Grid: 1