RT，思路是每次覆盖 $1$ 数量最少的 L。

WA on #4

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int T,n,m,a[505][505];
struct node{
	int x,y,flg,cnt;
	inline bool operator <(const node &o) const{
		return cnt>o.cnt;
	}
};
priority_queue<node> q;
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				scanf("%1d",&a[i][j]);
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j){
				if(i>1&&j>1){
					q.push(node({i,j,1,a[i][j]+a[i-1][j]+a[i][j-1]}));
					q.push(node({i,j,5,a[i][j]+a[i-1][j]+a[i-1][j-1]}));
					q.push(node({i,j,9,a[i][j]+a[i][j-1]+a[i-1][j-1]}));
				}
				if(i>1&&j<m){
					q.push(node({i,j,2,a[i][j]+a[i-1][j]+a[i][j+1]}));
					q.push(node({i,j,6,a[i][j]+a[i-1][j]+a[i-1][j+1]}));
					q.push(node({i,j,10,a[i][j]+a[i][j+1]+a[i-1][j+1]}));
				}
				if(i<n&&j>1){
					q.push(node({i,j,3,a[i][j]+a[i+1][j]+a[i][j-1]}));
					q.push(node({i,j,7,a[i][j]+a[i+1][j]+a[i+1][j-1]}));
					q.push(node({i,j,11,a[i][j]+a[i][j-1]+a[i+1][j-1]}));
				}
				if(i<n&&j<m){
					q.push(node({i,j,4,a[i][j]+a[i+1][j]+a[i][j+1]}));
					q.push(node({i,j,8,a[i][j]+a[i+1][j]+a[i+1][j+1]}));
					q.push(node({i,j,12,a[i][j]+a[i][j+1]+a[i+1][j+1]}));
				}
			}
		int cnt=0;
		while(q.size()){
			node t=q.top();
			q.pop();
			int x=t.x,y=t.y;
			int a1,b1,a2,b2,a3,b3;
			if(t.flg==1){
				a1=x,b1=y;
				a2=x-1,b2=y;
				a3=x,b3=y-1;
			} else if(t.flg==2){
				a1=x,b1=y;
				a2=x-1,b2=y;
				a3=x,b3=y+1;
			} else if(t.flg==3){
				a1=x,b1=y;
				a2=x+1,b2=y;
				a3=x,b3=y-1;
			} else if(t.flg==4){
				a1=x,b1=y;
				a2=x+1,b2=y;
				a3=x,b3=y+1;
			} else if(t.flg==5){
				a1=x,b1=y;
				a2=x-1,b2=y;
				a3=x-1,b3=y-1;
			} else if(t.flg==6){
				a1=x,b1=y;
				a2=x-1,b2=y;
				a3=x-1,b3=y+1;
			} else if(t.flg==7){
				a1=x,b1=y;
				a2=x+1,b2=y;
				a3=x+1,b3=y-1;
			} else if(t.flg==8){
				a1=x,b1=y;
				a2=x+1,b2=y;
				a3=x+1,b3=y+1;
			} else if(t.flg==9){
				a1=x,b1=y;
				a2=x,b2=y-1;
				a3=x-1,b3=y-1;
			} else if(t.flg==10){
				a1=x,b1=y;
				a2=x,b2=y+1;
				a3=x-1,b3=y+1;
			} else if(t.flg==11){
				a1=x,b1=y;
				a2=x,b2=y-1;
				a3=x+1,b3=y-1;
			} else{
				a1=x,b1=y;
				a2=x,b2=y+1;
				a3=x+1,b3=y+1;
			}
			int X=a[a1][b1],Y=a[a2][b2],Z=a[a3][b3];
			a[a1][b1]=a[a2][b2]=a[a3][b3]=0;
			if(!X&&!Y&&!Z)
				continue;
			++cnt;
			if(X){
				int i=a1,j=b1;
				if(i>1&&j>1)
					q.push(node({i,j,1,a[i][j]+a[i-1][j]+a[i][j-1]}));
				if(i>1&&j<m)
					q.push(node({i,j,2,a[i][j]+a[i-1][j]+a[i][j+1]}));
				if(i<n&&j>1)
					q.push(node({i,j,3,a[i][j]+a[i+1][j]+a[i][j-1]}));
				if(i<n&&j<m)
					q.push(node({i,j,4,a[i][j]+a[i+1][j]+a[i][j+1]}));
			}
			if(Y){
				int i=a2,j=b2;
				if(i>1&&j>1)
					q.push(node({i,j,1,a[i][j]+a[i-1][j]+a[i][j-1]}));
				if(i>1&&j<m)
					q.push(node({i,j,2,a[i][j]+a[i-1][j]+a[i][j+1]}));
				if(i<n&&j>1)
					q.push(node({i,j,3,a[i][j]+a[i+1][j]+a[i][j-1]}));
				if(i<n&&j<m)
					q.push(node({i,j,4,a[i][j]+a[i+1][j]+a[i][j+1]}));
			}
			if(Z){
				int i=a3,j=b3;
				if(i>1&&j>1)
					q.push(node({i,j,1,a[i][j]+a[i-1][j]+a[i][j-1]}));
				if(i>1&&j<m)
					q.push(node({i,j,2,a[i][j]+a[i-1][j]+a[i][j+1]}));
				if(i<n&&j>1)
					q.push(node({i,j,3,a[i][j]+a[i+1][j]+a[i][j-1]}));
				if(i<n&&j<m)
					q.push(node({i,j,4,a[i][j]+a[i+1][j]+a[i][j+1]}));
			}
		}
		printf("%d\n",cnt);
	}
	return 0;
}