Advertisement
Guest User

Untitled

a guest
May 24th, 2017
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.61 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Solution {
  5.  
  6.     class Pair {
  7.         int a;
  8.         int b;
  9.  
  10.         public Pair(int a, int b) {
  11.             this.a = a;
  12.             this.b = b;
  13.         }
  14.     }
  15.  
  16.     void solve() {
  17.         int n = in.nextInt();
  18.         int m = in.nextInt();
  19.         char[][] map = in.nextCharMap(n, m);
  20.         int ans = 0;
  21.         for (int i = 0; i < n; i++) {
  22.             for (int j = 0; j < m; j++) {
  23.                 if (map[i][j] == 'x') {
  24.                     ans++;
  25.                     bfs(i, j, map, n, m);
  26.                 }
  27.             }
  28.         }
  29.         out.println(ans);
  30.  
  31.     }
  32.  
  33.     void bfs(int i, int j, char[][] map, int n, int m) {
  34.         ArrayDeque<Pair> queue = new ArrayDeque<>();
  35.         queue.add(new Pair(i, j));
  36.         while (!queue.isEmpty()) {
  37.             Pair cur = queue.poll();
  38.             map[cur.a][cur.b] = 'o';
  39.             if (cur.a - 1 >= 0 && map[cur.a - 1][cur.b] == 'x') {
  40.                 queue.add(new Pair(cur.a - 1, cur.b));
  41.             }
  42.             if (cur.a + 1 < n && map[cur.a + 1][cur.b] == 'x') {
  43.                 queue.add(new Pair(cur.a + 1, cur.b));
  44.             }
  45.             if (cur.b - 1 >= 0 && map[cur.a][cur.b - 1] == 'x') {
  46.                 queue.add(new Pair(cur.a, cur.b - 1));
  47.             }
  48.             if (cur.b + 1 < m && map[cur.a][cur.b + 1] == 'x') {
  49.                 queue.add(new Pair(cur.a, cur.b + 1));
  50.             }
  51.         }
  52.     }
  53.  
  54.  
  55.     Scanner in;
  56.     PrintWriter out;
  57.  
  58.     void run() {
  59.         try {
  60.             in = new Scanner(new File("A.in"));
  61.             out = new PrintWriter(new File("A.out"));
  62.  
  63.             solve();
  64.  
  65.             out.close();
  66.         } catch (FileNotFoundException e) {
  67.             e.printStackTrace();
  68.         }
  69.     }
  70.  
  71.     void runIO() {
  72.  
  73.         in = new Scanner(System.in);
  74.         out = new PrintWriter(System.out);
  75.  
  76.         solve();
  77.  
  78.         out.close();
  79.     }
  80.  
  81.     class Scanner {
  82.         BufferedReader br;
  83.         StringTokenizer st;
  84.  
  85.         public Scanner(File f) {
  86.             try {
  87.                 br = new BufferedReader(new FileReader(f));
  88.             } catch (FileNotFoundException e) {
  89.                 e.printStackTrace();
  90.             }
  91.         }
  92.  
  93.         public Scanner(InputStream f) {
  94.             br = new BufferedReader(new InputStreamReader(f));
  95.         }
  96.  
  97.         String next() {
  98.             while (st == null || !st.hasMoreTokens()) {
  99.                 String s = null;
  100.                 try {
  101.                     s = br.readLine();
  102.                 } catch (IOException e) {
  103.                     e.printStackTrace();
  104.                 }
  105.                 if (s == null)
  106.                     return null;
  107.                 st = new StringTokenizer(s);
  108.             }
  109.             return st.nextToken();
  110.         }
  111.  
  112.         private boolean isSpaceChar(int c) {
  113.             return !(c >= 33 && c <= 126);
  114.         }
  115.  
  116.         private int skip() {
  117.             int b;
  118.             while ((b = read()) != -1 && isSpaceChar(b)) ;
  119.             return b;
  120.         }
  121.  
  122.         private int read() {
  123.             int res = -1;
  124.             try {
  125.                 res = br.read();
  126.             } catch (IOException e) {
  127.                 e.printStackTrace();
  128.             }
  129.             return res;
  130.         }
  131.  
  132.         char[] nextCharArray(int size) {
  133.             char[] buf = new char[size];
  134.             int b = skip(), p = 0;
  135.             while (p < size && !(isSpaceChar(b))) {
  136.                 buf[p++] = (char) b;
  137.                 b = read();
  138.             }
  139.             return size == p ? buf : Arrays.copyOf(buf, p);
  140.         }
  141.  
  142.         char[][] nextCharMap(int n, int m) {
  143.             char[][] map = new char[n][];
  144.             for (int i = 0; i < n; i++) {
  145.                 map[i] = nextCharArray(m);
  146.             }
  147.             return map;
  148.         }
  149.  
  150.         boolean hasMoreTokens() {
  151.             while (st == null || !st.hasMoreTokens()) {
  152.                 String s = null;
  153.                 try {
  154.                     s = br.readLine();
  155.                 } catch (IOException e) {
  156.                     e.printStackTrace();
  157.                 }
  158.                 if (s == null)
  159.                     return false;
  160.                 st = new StringTokenizer(s);
  161.             }
  162.             return true;
  163.         }
  164.  
  165.         int nextInt() {
  166.             return Integer.parseInt(next());
  167.         }
  168.  
  169.         long nextLong() {
  170.             return Long.parseLong(next());
  171.         }
  172.  
  173.         double nextDouble() {
  174.             return Double.parseDouble(next());
  175.         }
  176.     }
  177.  
  178.     public static void main(String[] args) {
  179.         new Solution().runIO();
  180.     }
  181. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement