fork download
copy 
  1. import java.util.*;
  2. import java.io.*; 
  3. import java.text.DecimalFormat;
  4.  
  5. public class Main{
  6.     final long mod = (int)998244353, IINF = (long)1e18;
  7.     final int MAX = (int)2e5+1, MX = (int)1e7+1, INF = (int)1e9, root = 3;
  8.     DecimalFormat df = new DecimalFormat("0.0000000000000");
  9.     double eps = 1e-9, PI = 3.141592653589793238462643383279502884197169399375105820974944;
  10.     static boolean multipleTC = false, memory = false;
  11.     FastReader in;PrintWriter out;
  12.     public static void main(String[] args) throws Exception{
  13.         if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
  14.         else new Main().run();
  15.     }
  16.  
  17.     void run() throws Exception{
  18.         in = new FastReader();
  19.         out = new PrintWriter(System.out);
  20.         for(int i = 1, T= (multipleTC)?ni():1; i<= T; i++)solve(i);
  21.         out.flush();
  22.         out.close();
  23.     }
  24.     int ans = 0;
  25.     void solve(int TC) throws Exception{
  26.         int n = ni(), m = ni();
  27.         map = new int[m*2];
  28.         int[] set = new int[m*2];
  29.         ans = 0;
  30.         String s;
  31.         boolean[] st = new boolean[m*2];
  32.         for(int i = 0; i< n; i++){
  33.             s = n();
  34.             for(int j = 0; j< s.length(); j++){
  35.                 char c = s.charAt(j);
  36.                 int x = (c<='9')?(c-'0'):(c-'A'+10);
  37.                 for(int k = 0; k< 4; k++){
  38.                     st[m+4*j+k] = ((x>>(3-k))&1)==1;
  39.                     if(st[m+4*j+k])ans++;
  40.                     set[m+4*j+k] = m+4*j+k;
  41.                 }
  42.             }
  43.             for(int j = 0; j< m; j++)if(st[j] && st[j+m])union(set,j,j+m);
  44.             for(int j = m+1; j< 2*m; j++)if(st[j] && st[j-1])union(set,j-1,j);
  45.             uniq(set);
  46.             for(int j = 0; j< m; j++)st[j] = st[j+m];
  47.         }
  48.         pn(ans);
  49.     }
  50.     int find(int[] set, int a){
  51.         if(set[a]!=a)set[a] = find(set,set[a]);
  52.         return set[a];
  53.     }
  54.     void union(int[] set, int a, int b){
  55.         a = find(set,a);b = find(set,b);
  56.         if(a==b)return;
  57.         set[b] = a;
  58.         ans--;
  59.     }
  60.     int[] map;
  61.     void uniq(int[] set){
  62.         for(int i = 0; i<map.length; i++)map[i] = -1;
  63.         int cur = 0;
  64.         for(int i =  set.length/2; i< set.length; i++){
  65.             if(map[set[i]]==-1)map[set[i]] = cur++;
  66.         }
  67.         for(int i = 0; i< set.length/2; i++)set[i] = map[set[i+set.length/2]];
  68.     }
  69.  
  70.     int[] sort(int[] a){
  71.         if(a.length==1)return a;
  72.         int mid = a.length/2;
  73.         int[] b = sort(Arrays.copyOfRange(a,0,mid)), c = sort(Arrays.copyOfRange(a,mid,a.length));
  74.         for(int i = 0, j = 0, k = 0; i< a.length; i++){
  75.             if(j<b.length && k<c.length){
  76.                 if(b[j]<c[k])a[i] = b[j++];
  77.                 else a[i] = c[k++];
  78.             }else if(j<b.length)a[i] = b[j++];
  79.             else a[i] = c[k++];
  80.         }
  81.         return a;
  82.     }
  83.  
  84.     long[] sort(long[] a){
  85.         if(a.length==1)return a;
  86.         int mid = a.length/2;
  87.         long[] b = sort(Arrays.copyOfRange(a,0,mid)), c = sort(Arrays.copyOfRange(a,mid,a.length));
  88.         for(int i = 0, j = 0, k = 0; i< a.length; i++){
  89.             if(j<b.length && k<c.length){
  90.                 if(b[j]<c[k])a[i] = b[j++];
  91.                 else a[i] = c[k++];
  92.             }else if(j<b.length)a[i] = b[j++];
  93.             else a[i] = c[k++];
  94.         }
  95.         return a;
  96.     }
  97.  
  98.     long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
  99.     int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
  100.     int bitcount(long n){return (n==0)?0:(1+bitcount(n&(n-1)));}
  101.     void p(Object o){out.print(o);}
  102.     void pn(Object o){out.println(o);}
  103.     void pni(Object o){out.println(o);out.flush();}
  104.     String n(){return in.next();}
  105.     String nln(){return in.nextLine();}
  106.     int ni(){return Integer.parseInt(in.next());}
  107.     long nl(){return Long.parseLong(in.next());}
  108.     double nd(){return Double.parseDouble(in.next());}
  109.  
  110.     class FastReader{
  111.         BufferedReader br;
  112.         StringTokenizer st;
  113.         public FastReader(){
  114.             br = new BufferedReader(new InputStreamReader(System.in));
  115.         }
  116.  
  117.         public FastReader(String s) throws Exception{
  118.             br = new BufferedReader(new FileReader(s));
  119.         }
  120.  
  121.         String next(){
  122.             while (st == null || !st.hasMoreElements()){
  123.                 try{
  124.                     st = new StringTokenizer(br.readLine());
  125.                 }catch (IOException  e){
  126.                     e.printStackTrace();
  127.                 }
  128.             }
  129.             return st.nextToken();
  130.         }
  131.  
  132.         String nextLine(){
  133.             String str = "";
  134.             try{    
  135.                 str = br.readLine();
  136.             }catch (IOException e){
  137.                 e.printStackTrace();
  138.             }   
  139.             return str;
  140.         }
  141.     }
  142. }
Success #stdin #stdout 0.11s 29244KB
comments (?)
stdin
copy 
3 16

9CFD

E9A7

9BAF
stdout
copy 
4
https://ideone.com/CcizLE
language:
Java (HotSpot 12)
created:
5 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!