Untitled

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <algorithm>

using namespace std;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int bfs(vector<vector<char>> &MAP, set<char> &keys) {
    int n = MAP.size(), m = MAP[0].size();
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    queue<pair<int, int>> deq;
    deq.push({0, 0});
    int cnt = 0;
    bool new_key_found = false;

    while (!deq.empty()) {
        int y = deq.front().first;
        int x = deq.front().second;
        deq.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i], nx = x + dx[i];
            if (0 <= nx && nx < m && 0 <= ny && ny < n && MAP[ny][nx] != '1') {
                if (!vis[ny][nx]) {
                    vis[ny][nx] = true;
                    char c = MAP[ny][nx];

                    if (c == '0') {
                        deq.push({ny, nx});
                    } else if ('a' <= c && c <= 'z') {
                        MAP[ny][nx] = '0';
                        keys.insert(c);
                        new_key_found = true;
                    } else if ('A' <= c && c <= 'Z' && keys.count(tolower(c))) {
                        MAP[ny][nx] = '0';
                        deq.push({ny, nx});
                    } else if (c == '$') {
                        MAP[ny][nx] = '0';
                        cnt++;
                    }
                }
            }
        }
    }

    return new_key_found ? -cnt : cnt;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<vector<char>> MAP(n + 2, vector<char>(m + 2, '0'));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> MAP[i][j];
                if (MAP[i][j] == '*') MAP[i][j] = '1';
                if (MAP[i][j] == '.') MAP[i][j] = '0';
            }
        }

        string input_keys;
        cin >> input_keys;
        set<char> keys(input_keys.begin(), input_keys.end());
        if (input_keys == "0") keys.clear();

        int res = 0;
        while (1) {
            int cnt = bfs(MAP, keys);
            if (cnt < 0) {
                res -= cnt;
            } else {
                res += cnt;
                break;
            }
        }
        cout << res << endl;
        for(int i=0;i<n+2;i++){
            for(int j = 0;j<m+2;j++){
                cout << MAP[i][j] << " ";
            }
            cout << '\n';
        }
    }

    return 0;
}