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 class Point {
  11.         int x, y;
  12.         Point(int x, int y) {
  13.             this.x = x;
  14.             this.y = y;
  15.         }
  16.     }
  17.  
  18.     public static void main(String[] args) {
  19.         Scanner in = new Scanner(System.in);
  20.  
  21.         int n = in.nextInt(), m = in.nextInt();
  22.         int dx[] = {-1, 0, 1, 0};
  23.         int dy[] = {0, -1, 0, 1};
  24.         in.nextLine();
  25.  
  26.         String[] ar = new String[n];
  27.         int[][] dis = new int[n][m];
  28.         boolean[][] vis = new boolean[n][m];
  29.         Point start = null, end = null;
  30.  
  31.         for (int i = 0; i < n; i++) {
  32.             ar[i] = in.nextLine();
  33.             for (int j = 0; j < m; j++) {
  34.                 char ch = ar[i].charAt(j);
  35.                 if (ch == 'E') {
  36.                     end = new Point(i, j);
  37.                 } else if (ch == 'S') {
  38.                     start = new Point(i, j);
  39.                 }
  40.             }
  41.         }
  42.  
  43.         Queue<Point> q = new ArrayDeque<>();
  44.         if (end != null) {
  45.             q.add(end);
  46.             vis[end.x][end.y] = true;
  47.         }
  48.  
  49.         int steps = 0;
  50.  
  51.         while (!q.isEmpty()) {
  52.             Point p = q.poll();
  53.             int curDist = dis[p.x][p.y];
  54.  
  55.             if (p.x == start.x && p.y == start.y) {
  56.                 steps = curDist;
  57.             }
  58.  
  59.             for (int i = 0; i < 4; i++) {
  60.                 int newx = p.x + dx[i], newy = p.y + dy[i];
  61.                 if (newx >= 0 && newx < n && newy >= 0 && newy < m 
  62.                         && !vis[newx][newy] && ar[newx].charAt(newy) != 'T') {
  63.                     q.add(new Point(newx, newy));
  64.                     vis[newx][newy] = true;
  65.                     dis[newx][newy] = curDist + 1;
  66.                 }
  67.             }
  68.         }
  69.  
  70.         int ans = 0;
  71.         for (int i = 0; i < n; i++) {
  72.             for (int j = 0; j < m; j++) {
  73.                 char ch = ar[i].charAt(j);
  74.                 if (Character.isDigit(ch) && vis[i][j] && dis[i][j] <= steps) {
  75.                     ans += ch - '0';
  76.                 }
  77.             }
  78.         }
  79.  
  80.         System.out.println(ans);
  81.         in.close();
  82.     }
  83. }
Success #stdin #stdout 0.12s 54660KB
comments (?)
stdin
copy 
5 7
000E0T3
T0TT0T0
010T0T0
2T0T0T0
0T0S000
stdout
copy 
3
https://ideone.com/RbkMs6
language:
Java (HotSpot 12)
created:
6 days 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!