D.cpp

/*
 * VJUDGE D - Aquarium
 * author: roy4801
 * (C++)
 */
#include <bits/stdc++.h>

using namespace std;

#define PROB "D"
#define TESTC ""

#define USE_CPPIO() ios_base::sync_with_stdio(0); cin.tie(0)
typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int, int> P;
typedef pair<LL, LL> PLL;
#define F first
#define S second
#define INF 0x3f3f3f3f
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PPB pop_back
#define PF push_front
#define PPF pop_front
#define L 100
#define preS(x) ((x) - (c+1))
#define preB(x) (preS(x)+1)
char m[L+5][L+5];
int w[L+5][L+5];
int kase, C=1;
int r, c; // i, j
int ans;
struct E
{
	E(int a, int b, int wei)
	{
		this->a = a;
		this->b = b;
		this->wei = wei;
	}
	int a, b, wei;
	friend bool operator<(const E &lhs, const E &rhs)
	{
		return lhs.wei < rhs.wei;
	}
};
vector<E> e;
struct disjoint
{
	int p[100005];
	void init() {
		for(int i = 0; i <= 2*L+5; i++) p[i] = i;
	}
	int find(int x) {
		return p[x] == x ? x : (p[x] = find(p[x]));
	}
	void uni(int a, int b) {
		// printf(">> uni %d %d\n", a, b);
		p[find(a)] = find(b);
	}
	bool isSame(int a, int b) {
		return find(a) == find(b);
	}
};
disjoint d;
int main()
{
	#ifdef DBG
	freopen("./testdata/" PROB TESTC ".in", "r", stdin);
	freopen("./testdata/" PROB ".out", "w", stdout);
	#endif
	cin >> kase;
	while(kase-- && cin >> r >> c)
	{
		d.init();
		e.clear();
		ans = 0;
		//
		cin.get();
		for(int i = 0; i < r; i++)
		{
			for(int j = 0; j < c; j++)
				cin >> m[i][j];
			cin.get();
		}
		for(int i = 0; i < r; i++)
			for(int j = 0; j < c; j++)
				cin >> w[i][j];
		//
		int ii = 1; // current small number
		for(int i = 0; i < r; i++)
		{
			for(int j = 0; j < c; j++)
			{
				// printf("> cur %d %d %d %d\n", ii, ii+1, preS(ii), preB(ii));
				e.PB(E(ii, ii+1, w[i][j]));
				if(i > 0)
				{
					if(m[i-1][j] == '/')
					{
						if(m[i][j] == '/')
							e.PB(E(ii, preB(ii), 0));
						else
							e.PB(E(ii+1, preB(ii), 0));
					}
					else /* \ */
					{
						if(m[i][j] == '/')
							e.PB(E(ii, preS(ii), 0));
						else
							e.PB(E(ii+1, preS(ii), 0));
					}
				}
				ii++;
			}
			ii++;
		}
		sort(e.begin(), e.end());

		// for(auto &i : e)
		// 	printf("> %d %d %d\n", i.a, i.b, i.wei);

		for(auto &i : e)
		{
			if(!d.isSame(i.a, i.b))
			{
				ans += i.wei;
				d.uni(i.a, i.b);
			}
		}
		printf("Case %d: %d\n", C++, ans);
	}

	return 0;
}