fork(1) download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.*;
  4.  
  5. class Solution {
  6.     public static void main(String[] args) {
  7.         Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
  8.         int t = Integer.parseInt(in.nextLine()); // Scanner has functions to read ints, longs, strings, chars, etc.
  9.         for (int i = 1; i <= t; ++i) {
  10.             // Square dance
  11.             int row = in.nextInt();
  12.             int col = in.nextInt();
  13.             Dancer[][] dancers = new Dancer[row][col];
  14.             for (int r = 0; r < row; r++) {
  15.                 for (int c = 0; c < col; c++) {
  16.                     Dancer d = new Dancer(in.nextInt());
  17.                     if (r>0) {
  18.                         d.top = dancers[r-1][c];
  19.                         dancers[r-1][c].bottom = d;
  20.                     }
  21.  
  22.                     if (c>0) {
  23.                         d.left = dancers[r][c-1];
  24.                         dancers[r][c-1].right = d;
  25.                     }
  26.                     dancers[r][c] = d;
  27.                 }
  28.             }
  29.  
  30.             System.out.println("Case #" + i + ": "+squareDance(dancers));
  31.         }
  32.     }
  33.  
  34.     private static int squareDance(Dancer[][] dancers) {
  35.         int totalInterest = 0;
  36.         while (true) {
  37.             int roundInterest = 0;
  38.             List<Dancer> eliminatedDancers = new ArrayList();
  39.             for (int r=0; r<dancers.length; r++) {
  40.                 for (int c=0; c<dancers[0].length; c++) {
  41.                     Dancer d = dancers[r][c];
  42.                     if (!d.isEliminated) {
  43.                         roundInterest += d.skill;
  44.                     } else {
  45.                         continue;
  46.                     }
  47.                     if (!d.isCompeted() || !d.losing()) {
  48.                         continue;
  49.                     } else {
  50.                         eliminatedDancers.add(d);
  51.                     }
  52.                 }
  53.             }
  54.             totalInterest += roundInterest;
  55.             if (eliminatedDancers.size() == 0) {
  56.                 break;
  57.             } else {
  58.                 for (Dancer d: eliminatedDancers) {
  59.                     eliminateDancer(d);
  60.                 }
  61.             }
  62.         }
  63.         return totalInterest;
  64.     }
  65.  
  66.     private static void eliminateDancer(Dancer d) {
  67.         d.isEliminated = true;
  68.         if (d.top!=null) {
  69.             d.top.bottom = d.bottom;
  70.         }
  71.         if (d.left!=null) {
  72.             d.left.right = d.right;
  73.         }
  74.         if (d.right!=null) {
  75.             d.right.left = d.left;
  76.         }
  77.         if (d.bottom!=null) {
  78.             d.bottom.top = d.top;
  79.         }
  80.     }
  81.  
  82.     static class Dancer {
  83.         private int skill;
  84.         private boolean isEliminated = false;
  85.         private Dancer top = null;
  86.         private Dancer bottom = null;
  87.         private Dancer left = null;
  88.         private Dancer right = null;
  89.  
  90.         public Dancer(int s) {
  91.             skill = s;
  92.         }
  93.  
  94.         public boolean isCompeted() {
  95.             return (top!=null || bottom!=null || left!=null || right!=null);
  96.         }
  97.  
  98.         public boolean losing() {
  99.             int skillSum = 0;
  100.             int count = 0;
  101.             if (top!=null) {
  102.                 skillSum += top.skill;
  103.                 count++;
  104.             }
  105.             if (bottom!=null) {
  106.                 skillSum += bottom.skill;
  107.                 count++;
  108.             }
  109.             if (left!=null) {
  110.                 skillSum += left.skill;
  111.                 count++;
  112.             }
  113.             if (right!=null) {
  114.                 skillSum += right.skill;
  115.                 count++;
  116.             }
  117.  
  118.             return skill*count < skillSum;
  119.         }
  120.     }
  121. }
Success #stdin #stdout 0.13s 37732KB
comments (?)
stdin
copy 
4
1 1
15
3 3
1 1 1
1 2 1
1 1 1
1 3
3 1 2
1 3
1 2 3
stdout
copy 
Case #1: 15
Case #2: 16
Case #3: 14
Case #4: 14
https://ideone.com/yDdiMS
language:
Java (HotSpot 12)
created:
4 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!