fork(5) download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <sstream>
  4. #include <string>
  5. #include <fstream>
  6. #include <iostream>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <cmath>
  10.  
  11. /*
  12.  * the strassen algorithm implementation was taken from
  13.  * https://g...content-available-to-author-only...b.com/MartinThoma/matrix-multiplication
  14.  * */
  15.  
  16. // Set LEAF_SIZE to 1 if you want to the pure strassen algorithm
  17. // otherwise, the ikj-algorithm will be applied when the split
  18. // matrices are as small as LEAF_SIZE x LEAF_SIZE
  19. int leafsize;
  20.  
  21. using namespace std;
  22.  
  23. typedef vector<int> vi;
  24.  
  25. /*
  26.  * Implementation of the strassen algorithm, similar to 
  27.  * http://e...content-available-to-author-only...a.org/w/index.php?title=Strassen_algorithm&oldid=498910018#Source_code_of_the_Strassen_algorithm_in_C_language
  28.  */
  29.  
  30. void strassen(vector< vector<int> > &A, 
  31.               vector< vector<int> > &B, 
  32.               vector< vector<int> > &C, unsigned int tam);
  33. unsigned int nextPowerOfTwo(int n);
  34. void strassenR(vector< vector<int> > &A, 
  35.               vector< vector<int> > &B, 
  36.               vector< vector<int> > &C, 
  37.               int tam);
  38. void sum(vector< vector<int> > &A, 
  39.          vector< vector<int> > &B, 
  40.          vector< vector<int> > &C, int tam);
  41. void subtract(vector< vector<int> > &A, 
  42.               vector< vector<int> > &B, 
  43.               vector< vector<int> > &C, int tam);
  44.  
  45. void printMatrix(vector< vector<int> > matrix, int n);
  46. void read(string filename, vector< vector<int> > &A, vector< vector<int> > &B);
  47.  
  48. void ikjalgorithm(vector< vector<int> > A, 
  49.                                    vector< vector<int> > B,
  50.                                    vector< vector<int> > &C, int n) {
  51.     for (int i = 0; i < n; i++) {
  52.         for (int k = 0; k < n; k++) {
  53.             for (int j = 0; j < n; j++) {
  54.                 C[i][j] += A[i][k] * B[k][j];
  55.             }
  56.         }
  57.     }
  58. }
  59.  
  60. void strassenR(vector< vector<int> > &A, 
  61.               vector< vector<int> > &B, 
  62.               vector< vector<int> > &C, int tam) {
  63.     if (tam <= leafsize) {
  64.         ikjalgorithm(A, B, C, tam);
  65.         return;
  66.     }
  67.  
  68.     // other cases are treated here:
  69.     else {
  70.         int newTam = tam/2;
  71.         vector<int> inner (newTam);
  72.         vector< vector<int> > 
  73.             a11(newTam,inner), a12(newTam,inner), a21(newTam,inner), a22(newTam,inner),
  74.             b11(newTam,inner), b12(newTam,inner), b21(newTam,inner), b22(newTam,inner),
  75.               c11(newTam,inner), c12(newTam,inner), c21(newTam,inner), c22(newTam,inner),
  76.             p1(newTam,inner), p2(newTam,inner), p3(newTam,inner), p4(newTam,inner), 
  77.             p5(newTam,inner), p6(newTam,inner), p7(newTam,inner),
  78.             aResult(newTam,inner), bResult(newTam,inner);
  79.  
  80.         int i, j;
  81.  
  82.         //dividing the matrices in 4 sub-matrices:
  83.         for (i = 0; i < newTam; i++) {
  84.             for (j = 0; j < newTam; j++) {
  85.                 a11[i][j] = A[i][j];
  86.                 a12[i][j] = A[i][j + newTam];
  87.                 a21[i][j] = A[i + newTam][j];
  88.                 a22[i][j] = A[i + newTam][j + newTam];
  89.  
  90.                 b11[i][j] = B[i][j];
  91.                 b12[i][j] = B[i][j + newTam];
  92.                 b21[i][j] = B[i + newTam][j];
  93.                 b22[i][j] = B[i + newTam][j + newTam];
  94.             }
  95.         }
  96.  
  97.         // Calculating p1 to p7:
  98.  
  99.         sum(a11, a22, aResult, newTam); // a11 + a22
  100.         sum(b11, b22, bResult, newTam); // b11 + b22
  101.         strassenR(aResult, bResult, p1, newTam); // p1 = (a11+a22) * (b11+b22)
  102.  
  103.         sum(a21, a22, aResult, newTam); // a21 + a22
  104.         strassenR(aResult, b11, p2, newTam); // p2 = (a21+a22) * (b11)
  105.  
  106.         subtract(b12, b22, bResult, newTam); // b12 - b22
  107.         strassenR(a11, bResult, p3, newTam); // p3 = (a11) * (b12 - b22)
  108.  
  109.         subtract(b21, b11, bResult, newTam); // b21 - b11
  110.         strassenR(a22, bResult, p4, newTam); // p4 = (a22) * (b21 - b11)
  111.  
  112.         sum(a11, a12, aResult, newTam); // a11 + a12
  113.         strassenR(aResult, b22, p5, newTam); // p5 = (a11+a12) * (b22)   
  114.  
  115.         subtract(a21, a11, aResult, newTam); // a21 - a11
  116.         sum(b11, b12, bResult, newTam); // b11 + b12
  117.         strassenR(aResult, bResult, p6, newTam); // p6 = (a21-a11) * (b11+b12)
  118.  
  119.         subtract(a12, a22, aResult, newTam); // a12 - a22
  120.         sum(b21, b22, bResult, newTam); // b21 + b22
  121.         strassenR(aResult, bResult, p7, newTam); // p7 = (a12-a22) * (b21+b22)
  122.  
  123.         // calculating c21, c21, c11 e c22:
  124.  
  125.         sum(p3, p5, c12, newTam); // c12 = p3 + p5
  126.         sum(p2, p4, c21, newTam); // c21 = p2 + p4
  127.  
  128.         sum(p1, p4, aResult, newTam); // p1 + p4
  129.         sum(aResult, p7, bResult, newTam); // p1 + p4 + p7
  130.         subtract(bResult, p5, c11, newTam); // c11 = p1 + p4 - p5 + p7
  131.  
  132.         sum(p1, p3, aResult, newTam); // p1 + p3
  133.         sum(aResult, p6, bResult, newTam); // p1 + p3 + p6
  134.         subtract(bResult, p2, c22, newTam); // c22 = p1 + p3 - p2 + p6
  135.  
  136.         // Grouping the results obtained in a single matrix:
  137.         for (i = 0; i < newTam ; i++) {
  138.             for (j = 0 ; j < newTam ; j++) {
  139.                 C[i][j] = c11[i][j];
  140.                 C[i][j + newTam] = c12[i][j];
  141.                 C[i + newTam][j] = c21[i][j];
  142.                 C[i + newTam][j + newTam] = c22[i][j];
  143.             }
  144.         }
  145.     }
  146. }
  147.  
  148. unsigned int nextPowerOfTwo(int n) {
  149.     return pow(2, int(ceil(log2(n))));
  150. }
  151.  
  152. void strassen(vector< vector<int> > &A, 
  153.               vector< vector<int> > &B, 
  154.               vector< vector<int> > &C, unsigned int n) {
  155.     //unsigned int n = tam;
  156.     unsigned int m = nextPowerOfTwo(n);
  157.     vector<int> inner(m);
  158.     vector< vector<int> > APrep(m, inner), BPrep(m, inner), CPrep(m, inner);
  159.  
  160.     for(unsigned int i=0; i<n; i++) {
  161.         for (unsigned int j=0; j<n; j++) {
  162.             APrep[i][j] = A[i][j];
  163.             BPrep[i][j] = B[i][j];
  164.         }
  165.     }
  166.  
  167.     strassenR(APrep, BPrep, CPrep, m);
  168.     for(unsigned int i=0; i<n; i++) {
  169.         for (unsigned int j=0; j<n; j++) {
  170.             C[i][j] = CPrep[i][j];
  171.         }
  172.     }
  173. }
  174.  
  175. void sum(vector< vector<int> > &A, 
  176.          vector< vector<int> > &B, 
  177.          vector< vector<int> > &C, int tam) {
  178.     int i, j;
  179.  
  180.     for (i = 0; i < tam; i++) {
  181.         for (j = 0; j < tam; j++) {
  182.             C[i][j] = A[i][j] + B[i][j];
  183.         }
  184.     }
  185. }
  186.  
  187. void subtract(vector< vector<int> > &A, 
  188.               vector< vector<int> > &B, 
  189.               vector< vector<int> > &C, int tam) {
  190.     int i, j;
  191.  
  192.     for (i = 0; i < tam; i++) {
  193.         for (j = 0; j < tam; j++) {
  194.             C[i][j] = A[i][j] - B[i][j];
  195.         }
  196.     }   
  197. }
  198.  
  199. int getMatrixSize(string filename) {
  200.     string line;
  201.     ifstream infile;
  202.     infile.open (filename.c_str());
  203.     getline(infile, line);
  204.     return count(line.begin(), line.end(), '\t') + 1;
  205. }
  206.  
  207. void read(string filename, vector< vector<int> > &A, vector< vector<int> > &B) {
  208.     string line;
  209.     FILE* matrixfile = freopen(filename.c_str(), "r", stdin);
  210.  
  211.     if (matrixfile == 0) {
  212.         cerr << "Could not read file " << filename << endl;
  213.         return;
  214.     }
  215.  
  216.     int i = 0, j, a;
  217.     while (getline(cin, line) && !line.empty()) {
  218.         istringstream iss(line);
  219.         j = 0;
  220.         while (iss >> a) {
  221.             A[i][j] = a;
  222.             j++;
  223.         }
  224.         i++;
  225.     }
  226.  
  227.     i = 0;
  228.     while (getline(cin, line)) {
  229.         istringstream iss(line);
  230.         j = 0;
  231.         while (iss >> a) {
  232.             B[i][j] = a;
  233.             j++;
  234.         }
  235.         i++;
  236.     }
  237.  
  238.     fclose (matrixfile);
  239. }
  240.  
  241. void printMatrix(vector< vector<int> > matrix, int n) {
  242.     for (int i=0; i < n; i++) {
  243.         for (int j=0; j < n; j++) {
  244.             if (j != 0) {
  245.                 cout << "\t";
  246.             }
  247.             cout << matrix[i][j];
  248.         }
  249.         cout << endl;
  250.     }
  251. }
  252.  
  253. int main (int argc, char* argv[]) {
  254.     int n;
  255.     leafsize = 2048;
  256.     scanf("%d\n", &n);
  257.     vector<vi> A;
  258.     vector<int> inner (n);
  259.     vector< vector<int> > C(n, inner);
  260.     A.assign(n, vi());
  261.     for(int i = 0; i < n; i++) {
  262.         A[i].assign(n, 0);
  263.     }
  264.     for(int i = 0; i < n; i++) {
  265.         for(int j = 0; j < n; j++) {
  266.             char c;
  267.             scanf("%c", &c);
  268.             A[i][j] = c - '0';
  269.         } scanf("\n");
  270.     }
  271.     strassen(A, A, C, n);
  272.     /*
  273.     printMatrix(A, n);
  274.     printf("----------------------------------------\n");
  275.     printMatrix(C, n);
  276.     */
  277.     int ans = 0;
  278.     for(int i = 0; i < n; i++) {
  279.         for(int j = 0; j < n; j++) {
  280.             if(C[i][j] > 0 and i != j and A[i][j] != 1)
  281.                 ans++;
  282.         }
  283.     }
  284.     printf("%d\n", ans);
  285.     return 0;
  286. }
  287.  
  288.  
Success #stdin #stdout 0s 3504KB
comments (?)
stdin
copy 
4
0111
1000
1000
1000
stdout
copy 
6
https://ideone.com/DnZe1w
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!