Problem Link : D. Mushroom Kingdom
Category : Bitmask, Bfs
Contest : Intra AIUB Programming Contest 2024 (Senior)
#include "bits/stdc++.h"
using namespace std;
#define int long long int
#define endl '\n'
using pii = pair<int, int>;
int dr[] = {1, -1, 0, 0}; // 4 Direction
int dc[] = {0, 0, 1, -1};
void task() {
int n;
cin >> n;
vector<char> chars;
vector<vector<char>> grid(n + 1, vector<char>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> grid[i][j];
chars.push_back(grid[i][j]);
}
}
pii src;
cin >> src.first >> src.second;
pii des;
cin >> des.first >> des.second;
sort(chars.begin(), chars.end());
chars.erase(unique(chars.begin(), chars.end()), chars.end());
int ans = 10;
for (int mask = 0; mask < (1 << (int)chars.size()); mask++) {
set<int> validChars;
for (int i = 0; i < chars.size(); i++) {
if (mask >> i & 1) {
validChars.insert(chars[i]);
}
}
vector<vector<bool>> visited(n + 1, vector<bool>(n + 1));
queue<pii> pq;
if (validChars.count(grid[src.first][src.second])) {
pq.push(src);
visited[src.first][src.second] = 1;
}
while (pq.size()) {
pii cur = pq.front(); pq.pop();
for (int k = 0; k < 4; k++) {
int x = cur.first + dr[k];
int y = cur.second + dc[k];
if (x >= 1 and x <= n and y >= 1 and y <= n and visited[x][y] == 0 and validChars.count(grid[x][y])) {
pq.push(pii(x, y));
visited[x][y] = 1;
}
}
}
if (visited[des.first][des.second]) {
ans = min(ans, (int)__builtin_popcount(mask));
}
}
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cout.precision(12);
bool FILEIO = true; string FILE = "in.txt";
if (FILEIO and fopen(FILE.c_str(), "r")) {
freopen(FILE.c_str(), "r", stdin);
}
int tc;
cin >> tc;
for (int tcase = 1; tcase <= tc; tcase++) {
task();
}
}
