//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
const int N=1<<14|5;
char s[N];
int n,m,ans=0,f[N<<1],g[N];
inline int trans(const char&x) {
return isdigit(x)?x-'0':x-'A'+10;
}
inline int getf(int x) {
if(x<0||x>m-1)return 0;
return (trans(s[x/4])>>(3-x%4))&1;
}
inline int find(const int&x) {
return x!=f[x]?f[x]=find(f[x]):x;
}
inline void merge(int x,int y) {
int fx=find(x),fy=find(y);
fx!=fy?f[fx]=fy,--ans:0;
}
int main() {
scanf("%d%d",&n,&m);
memset(f,-1,sizeof(f));
rep(i,0,n-1){
scanf("%s",s);
rep(j,0,m-1)g[j]=getf(j); //获得二进制数位
rep(j,0,m-1)g[j]?++ans,f[j+m]=j+m:f[j+m]=-1;//计算1的个数，并初始化并查集的第二层
rep(j,0,m-1){
if(!g[j])continue;//0的话不需要与上层以及左边合并
if(~f[j])merge(j,j+m);//只要并查集第一层该位置的值不是-1，那么该位置就是1，合并第一层入第二层
if(getf(j-1))merge(j+m-1,j+m);//如果左边是1，那么合并左边1入右边
}
rep(j,0,m-1){//将第二层转化为第一层，滚动
if(g[j])
f[j]=find(j+m)-m;//-m是因为我们用是否小于m作为区别第一层与第二次的标志，现在滚动，就要让其小于m
else
f[j]=-1;
}
}
cout<<ans<<endl;
return 0;
}
撰写