下面是一道安徽大学校赛题的二分图最小权匹配。

显然，对于寻找最小权，我们只要将所有边权取负，再找对大权，此时的最大权的绝对值就是原图的二分图最小权。

此外，根据本题题意，所有棋子都要落到边上，可转化为二分图匹配问题，所有棋子对应左部点，而所有边上的格子对应为右部点，最终棋盘整理好即为所有棋子都要有对应的格子，即一个完美匹配，所以本题是一道二分图最小权值完美匹配问题。

不过本题转化为二分图匹配问题有一个前提：在考虑棋子移动时，我们无需考虑格子上已有的棋子，也就是说我们的棋子在移动时可穿过其他棋子，因为其他棋子也可发生移动。也就是说，我们甚至无需考虑棋子的移动，只需要考虑棋子与有效格子的匹配，这样原问题就变成了一个二分图匹配问题。

当格子数量小于棋子数量时，可特判为无解，这样场上的棋子与格子数最多不会超过800800，对于用 bfs 实现的 km 算法，时间复杂度为 O(m3)O(m^3) ，其中M为格子数。

本题的另一特点是要处理好边权，而边权也很明显，即为每个棋子到格子的曼哈顿距离。

//牛客，整理棋盘，二分图

#include<bits/stdc++.h>
#include<queue>
using namespace std;
typedef long long ll;

const int N = 405;
const int M = 805;
const int INF = 0x3f3f3f3f;
int n , m;

char c[N][N];
int a[M][M];
int posx[M], posy[M], pre[M];
int lx[M], ly[M], matchx[M], matchy[M];
int slack[M], d;
bool visx[M], visy[M];
queue<int> q;
int nl, nr;

void aug(int v) {
	while(v) {
		int t = matchx[pre[v]];
		matchx[pre[v]] = v;
		matchy[v] = pre[v];
		v = t;
	}
}

void bfs(int s) {

	for (int i = 1; i <= nr; i++) slack[i] = INF;

	memset(visx, 0, sizeof visx);
	memset(visy, 0, sizeof visy);
	memset(pre, 0, sizeof pre);

	while(!q.empty()) q.pop();
	q.push(s);

	while(1) {
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			visx[u] = 1;
			for (int v = 1; v <= nr; v++) {
				if (!visy[v]) {
					
					if (lx[u] + ly[v] - a[u][v] < slack[v]) {
						slack[v] = lx[u] + ly[v] - a[u][v];
						pre[v] = u;
					}
					
					if (!slack[v]) {
						visy[v] = 1;
						if (!matchy[v]) {
							aug(v);
							return;
						}else q.push(matchy[v]);
					}
					
				}
				
				
			}
		}
		
		d = INF;
		
		for (int i = 1; i <= nr; i++) {
			if (!visy[i]) d = min(d, slack[i]);
		}
		
		if (d == INF) break;
		
		for (int i = 1; i <= nl; i++) if (visx[i]) lx[i] -= d;
		for (int i = 1; i <= nr; i++) if (visy[i]) ly[i] += d;
		else slack[i] -= d;
		
		for (int i = 1 ; i <= nr; i++) {
			if (!visy[i] && !slack[i]) {
				visy[i] = 1;
				if (!matchy[i]) {
					aug(i);
					return;
				}else q.push(matchy[i]);
			}
		}
		
	}

}


void km() {

	for (int i = 1; i <= nl; i++) {
		for (int j = 1; j <= nr; j++) {
			lx[i] = max(lx[i], a[i][j]);
		}
	}

	for (int i = 1; i <= nl; i++) {
		bfs(i);
	}

}

void init() {
	for (int i = 0 ; i <= 800; i++) {
		posx[i] = -1;
		posy[i] = -1;
		matchy[i] = matchx[i] = 0;
		lx[i] = 0;
		ly[i] = 0;
	}
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		init();
		cin >> n >> m;

		int sp = n * 4 - 4;
		nl = m;
		nr = sp;
		int cnt = 1;

		for (int i = 1 ; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> c[i][j];
				if (c[i][j] == '#') {
					posx[cnt++] = (i-1) * n + j; // 记录棋子位置
				}

				a[i][j] = -INF;
			}
		}

		if (m > sp) {
			puts("-1");
			continue;
		}
		int cnty = 0;
		for (int i = 1; i <= n; i++) {
			posy[++cnty] = i;
		}

		for (int i = 2; i <= n-1; i++) {
			posy[++cnty] = (i - 1) * n + 1;
			posy[++cnty] = (i - 1) * n + n;
		}

		for (int i = 1; i <= n; i++) {
			posy[++cnty] = (n - 1) * n + i;
		}// 记录有效格子位置

		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= cnty; j++) {
				int x1 = (posx[i] - 1) / n + 1, x2 = (posy[j] - 1) / n + 1;
				int y1 = (posx[i] - 1) % n + 1, y2 = (posy[j] - 1) % n + 1;
				int w = abs(x1 - x2) + abs(y1 - y2);//处理边权
		//		cout << x1 << " " << y1 << "  ,  " << x2 << " " << y2 << ": " << w << endl; 
				a[i][j] = -1 * w;//边权取负
			}
		}

		km();
		
		int ans = 0;
		
		for (int i = 1; i <= nl; i++) ans += lx[i];
		for (int i = 1; i <= nr; i++) ans += ly[i];
		
		cout << abs(ans) << endl;

	}
	return 0;
}