fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     static int n, m;
  6.     static int[][] grid;
  7.     static boolean[][] vis;
  8.  
  9.     static int[] dx = {1, -1, 0, 0};
  10.     static int[] dy = {0, 0, 1, -1};
  11.  
  12.     static final int MAX = 1000000;
  13.     static final long MOD = 1000000007L;
  14.  
  15.     static ArrayList<ArrayList<int[]>> components = new ArrayList<>();
  16.  
  17.     static void bfs(int sx, int sy) {
  18.  
  19.         Queue<int[]> q = new LinkedList<>();
  20.         ArrayList<int[]> component = new ArrayList<>();
  21.  
  22.         q.offer(new int[]{sx, sy});
  23.         vis[sx][sy] = true;
  24.  
  25.         while (!q.isEmpty()) {
  26.  
  27.             int[] cur = q.poll();
  28.             int x = cur[0];
  29.             int y = cur[1];
  30.  
  31.             component.add(new int[]{x, y});
  32.  
  33.             for (int k = 0; k < 4; k++) {
  34.  
  35.                 int nx = x + dx[k];
  36.                 int ny = y + dy[k];
  37.  
  38.                 if (nx >= 0 && nx < n && ny >= 0 && ny < m
  39.                         && grid[nx][ny] > 0 && !vis[nx][ny]) {
  40.  
  41.                     vis[nx][ny] = true;
  42.                     q.offer(new int[]{nx, ny});
  43.                 }
  44.             }
  45.         }
  46.  
  47.         components.add(component);
  48.     }
  49.  
  50.     public static void main(String[] args) {
  51.  
  52.         Scanner sc = new Scanner(System.in);
  53.  
  54.         n = sc.nextInt();
  55.         m = sc.nextInt();
  56.  
  57.         grid = new int[n][m];
  58.         vis = new boolean[n][m];
  59.  
  60.         HashMap<Integer, Integer> freq = new HashMap<>();
  61.  
  62.         // Read grid and build frequency map
  63.         for (int i = 0; i < n; i++) {
  64.             for (int j = 0; j < m; j++) {
  65.  
  66.                 grid[i][j] = sc.nextInt();
  67.  
  68.                 if (grid[i][j] > 0) {
  69.                     freq.put(grid[i][j],
  70.                             freq.getOrDefault(grid[i][j], 0) + 1);
  71.                 }
  72.             }
  73.         }
  74.  
  75.         // Find connected components
  76.         for (int i = 0; i < n; i++) {
  77.             for (int j = 0; j < m; j++) {
  78.  
  79.                 if (grid[i][j] > 0 && !vis[i][j]) {
  80.                     bfs(i, j);
  81.                 }
  82.             }
  83.         }
  84.  
  85.         long answer = 0;
  86.  
  87.         // Process every component
  88.         for (ArrayList<int[]> component : components) {
  89.  
  90.             // Remove current component
  91.             for (int[] cell : component) {
  92.  
  93.                 int value = grid[cell[0]][cell[1]];
  94.  
  95.                 freq.put(value, freq.get(value) - 1);
  96.  
  97.                 if (freq.get(value) == 0)
  98.                     freq.remove(value);
  99.             }
  100.  
  101.             // Calculate SED of every cell
  102.             for (int[] cell : component) {
  103.  
  104.                 int value = grid[cell[0]][cell[1]];
  105.  
  106.                 long sed = 0;
  107.  
  108.                 // Find unreachable multiples
  109.                 for (int multiple = value; multiple <= MAX; multiple += value) {
  110.  
  111.                     if (freq.containsKey(multiple)) {
  112.  
  113.                         sed += (long) multiple * freq.get(multiple);
  114.  
  115.                     }
  116.                 }
  117.  
  118.                 answer = (answer + sed) % MOD;
  119.             }
  120.  
  121.             // Restore current component
  122.             for (int[] cell : component) {
  123.  
  124.                 int value = grid[cell[0]][cell[1]];
  125.  
  126.                 freq.put(value,
  127.                         freq.getOrDefault(value, 0) + 1);
  128.             }
  129.         }
  130.  
  131.         System.out.println(answer);
  132.     }
  133. }
Success #stdin #stdout 0.18s 74960KB
comments (?)
stdin
copy 
2 2
2  -1
-1  4
stdout
copy 
4
https://ideone.com/70hzCh
language:
Java (HotSpot 12)
created:
5 hours 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!