fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	static boolean[][] arr = {
  11.         {false, false, true, false, true},
  12.         {true, false, true, false, false},
  13.         {false, true, false, false, false},
  14.         {false, false, false, false, false},
  15.         {true, true, true, true, true}};
  16.  
  17.     public static boolean hasTrue(int startX, int startY, int endX, int endY){
  18.         for (int i = startY; i <= endY; i++)
  19.             for (int j = startX; j <= endX; j++)
  20.                 if (arr[i][j]) 
  21.                     return true;
  22.         return false;
  23.     }
  24.  
  25.     public static int calcCount(int startX, int startY, int endX, int endY) {
  26.         int count = 0;
  27.         for (int i = startY; i <= endY; ++i)
  28.             for (int j = startX; j <= endX; ++j)
  29.                 if (arr[i][j]) 
  30.                     ++count;
  31.         return count;
  32.     }
  33.  
  34.     public static int countTrues(int startX, int startY, int endX, int endY){
  35.         //Проверяем на наличие true
  36.         if (!hasTrue(startX, startY, endX, endY))
  37.             return 0;
  38.         //Если рассматриваем строку, столбец или один элемент, 
  39.         //то просто обычным циклом подсчитаем кол-во true
  40.         if (startX == endX || startY == endY)
  41.             return calcCount(startX, startY, endX, endY);
  42.         int count = 0;
  43.         int tEndX = (startX + endX) / 2;
  44.         int tEndY = (startY + endY) / 2;
  45.         //Подсчитываем true в левой верхней части матрицы
  46.         count += countTrues(startX, startY, tEndX, tEndY);
  47.         //В правой нижней части
  48.         count += countTrues(tEndX + 1, tEndY + 1, endX, endY);
  49.         //В левой нижней
  50.         count += countTrues(startX, tEndY + 1, tEndX, endY);
  51.         //И в правой нижней части
  52.         count += countTrues(tEndX + 1, startY, endX, tEndY);
  53.         return count;
  54.     }
  55.  
  56. 	public static void main(String[] args) {
  57. 		System.out.println(countTrues(0, 0, 4, 4));
  58. 	}
  59. }
Success #stdin #stdout 0.07s 32428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10
https://ideone.com/IXwUqN
language:
Java (HotSpot 12)
created:
3 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!