#include <bits/stdc++.h>
using namespace std;
/*
// vector = array dinamis
vector<int> arr;
cout << arr.size() << endl;
for(int i = 0; i < 10; i++)
arr.push_back(i);
cout << arr.size() << endl;
for(int i = 0; i < 10; i++)
cout << arr[i] << " ";
cout << endl;
*/
/*
pair<string, double> data;
data.first = "Ini string";
data.second = 1.2345;
data = make_pair("Ini string", 1.2345);
*/
vector<int> adjList[10];
bool visited[10];
int n = 7, e;
void dfs(int node) {
if(visited[node]) return;
visited[node] = true;
// cout << node << endl;
for(int i = 0; i < adjList[node].size(); i++)
dfs(adjList[node][i]);
}
int R, C;
string grid[100];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
void ff(int x, int y, char ganti) {
grid[x][y] = ganti;
int xx, yy;
for(int i = 0; i < 4; i++) {
xx = x+dx[i];
yy = y+dy[i];
if(xx >= 0 && xx < R && yy >= 0 && yy < C && grid[xx][yy] == '.')
ff(xx, yy, ganti);
}
}
int main() {
// Teori Graf
// Himpunan titik & himpunan garis yg masing2 menghubungkan 2 titik
// Directed vs undirected
// Weighted vs unweighted
// - 3 representasi graf (Adj Matrix, Adj List, Edge List)
// Adjacency Matrix
// pro: cepet, koding sederhana
// con: memory n^2
/*
int adjMat[6][6];
for(int i = 0; i < 6; i++)
for(int j = 0; j < 6; j++)
adjMat[i][j] = 0;
cin >> e;
for(int i = 0; i < e; i++) {
int a, b, c;
cin >> a >> b >> c;
adjMat[a][b] = c;
}
for(int i = 0; i < 6; i++) {
for(int j = 0; j < 6; j++)
printf("%2d ", adjMat[i][j]);
cout << endl;
}
*/
// Adjacency List
// pro: tengah2 antara adj Matrix & Edge list
// con: -
/*
vector<pair<int, int> > adjList[6];
cin >> e;
for(int i = 0; i < e; i++) {
int a, b, c;
cin >> a >> b >> c;
adjList[a].push_back(make_pair(b, c));
}
for(int i = 0; i < 6; i++) {
cout << i << ": ";
for(int j = 0; j < adjList[i].size(); j++)
cout << "(" << adjList[i][j].first << ", "
<< adjList[i][j].second << ") ";
cout << endl;
}
*/
// Object-oriented programming
// Edge List
/*
vector<pair<int, pair<int, int> > > edgeList;
cin >> e;
for(int i = 0; i < e; i++) {
int a, b, c;
cin >> a >> b >> c;
edgeList.push_back(make_pair(c, make_pair(a, b)));
}
sort(edgeList.begin(), edgeList.end());
for(int i = 0; i < e; i++)
cout << "(" << edgeList[i].second.first << ", "
<< edgeList[i].second.second << "): "
<< edgeList[i].first << endl;
*/
// - Graph traversal: Depth-First Search
/*
cin >> n >> e;
for(int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
adjList[a].push_back(b);
}
int start = 1;
for(int i = 0; i < n; i++)
visited[i] = false;
dfs(start);
for(int i = 0; i < n; i++)
if(visited[i])
cout << i << endl;
*/
// - Flood-fill on implicit graph
cin >> R >> C;
for(int i = 0; i < R; i++)
cin >> grid[i];
char ganti = 'a';
for(int i = 0; i < R; i++)
for(int j = 0; j < C; j++)
if(grid[i][j] == '.') {
ff(i, j, ganti++);
for(int k = 0; k < R; k++)
cout << grid[k] << endl;
cout << endl;
}
/*
##########
#..##....#
#####....#
#...###..#
#.....#..#
#....#####
#....#...#
##########
v
##########
#..##....#
#####....#
#aaa###..#
#aaaaa#..#
#aaaa#####
#aaaa#...#
##########
##########
#....#...#
#....#.#.#
######.###
#....#...#
#.######.#
#........#
##########
*/
return 0;
}
// https://o...content-available-to-author-only...s.com/contests/yhx2yb
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovKgovLyB2ZWN0b3IgPSBhcnJheSBkaW5hbWlzCnZlY3RvcjxpbnQ+IGFycjsKY291dCA8PCBhcnIuc2l6ZSgpIDw8IGVuZGw7CmZvcihpbnQgaSA9IDA7IGkgPCAxMDsgaSsrKQoJYXJyLnB1c2hfYmFjayhpKTsKY291dCA8PCBhcnIuc2l6ZSgpIDw8IGVuZGw7CmZvcihpbnQgaSA9IDA7IGkgPCAxMDsgaSsrKQoJY291dCA8PCBhcnJbaV0gPDwgIiAiOwpjb3V0IDw8IGVuZGw7CiovCgovKgpwYWlyPHN0cmluZywgZG91YmxlPiBkYXRhOwpkYXRhLmZpcnN0ID0gIkluaSBzdHJpbmciOwpkYXRhLnNlY29uZCA9IDEuMjM0NTsKZGF0YSA9IG1ha2VfcGFpcigiSW5pIHN0cmluZyIsIDEuMjM0NSk7CiovCgp2ZWN0b3I8aW50PiBhZGpMaXN0WzEwXTsKYm9vbCB2aXNpdGVkWzEwXTsKaW50IG4gPSA3LCBlOwoKdm9pZCBkZnMoaW50IG5vZGUpIHsKCWlmKHZpc2l0ZWRbbm9kZV0pIHJldHVybjsKCXZpc2l0ZWRbbm9kZV0gPSB0cnVlOwoJLy8gY291dCA8PCBub2RlIDw8IGVuZGw7Cglmb3IoaW50IGkgPSAwOyBpIDwgYWRqTGlzdFtub2RlXS5zaXplKCk7IGkrKykKCQlkZnMoYWRqTGlzdFtub2RlXVtpXSk7Cn0KCmludCBSLCBDOwpzdHJpbmcgZ3JpZFsxMDBdOwppbnQgZHhbXSA9IHswLCAxLCAwLCAtMX07CmludCBkeVtdID0gezEsIDAsIC0xLCAwfTsKCnZvaWQgZmYoaW50IHgsIGludCB5LCBjaGFyIGdhbnRpKSB7CglncmlkW3hdW3ldID0gZ2FudGk7CglpbnQgeHgsIHl5OwoJZm9yKGludCBpID0gMDsgaSA8IDQ7IGkrKykgewoJCXh4ID0geCtkeFtpXTsKCQl5eSA9IHkrZHlbaV07CgkJaWYoeHggPj0gMCAmJiB4eCA8IFIgJiYgeXkgPj0gMCAmJiB5eSA8IEMgJiYgZ3JpZFt4eF1beXldID09ICcuJykKCQkJZmYoeHgsIHl5LCBnYW50aSk7Cgl9Cn0KCmludCBtYWluKCkgewoJLy8gVGVvcmkgR3JhZgoJLy8gSGltcHVuYW4gdGl0aWsgJiBoaW1wdW5hbiBnYXJpcyB5ZyBtYXNpbmcyIG1lbmdodWJ1bmdrYW4gMiB0aXRpawoJLy8gRGlyZWN0ZWQgdnMgdW5kaXJlY3RlZAoJLy8gV2VpZ2h0ZWQgdnMgdW53ZWlnaHRlZAoJLy8gLSAzIHJlcHJlc2VudGFzaSBncmFmIChBZGogTWF0cml4LCBBZGogTGlzdCwgRWRnZSBMaXN0KQoJLy8gQWRqYWNlbmN5IE1hdHJpeAoJLy8gcHJvOiBjZXBldCwga29kaW5nIHNlZGVyaGFuYQoJLy8gY29uOiBtZW1vcnkgbl4yCgkvKgoJaW50IGFkak1hdFs2XVs2XTsKCWZvcihpbnQgaSA9IDA7IGkgPCA2OyBpKyspCgkJZm9yKGludCBqID0gMDsgaiA8IDY7IGorKykKCQkJYWRqTWF0W2ldW2pdID0gMDsKCWNpbiA+PiBlOwoJZm9yKGludCBpID0gMDsgaSA8IGU7IGkrKykgewoJCWludCBhLCBiLCBjOwoJCWNpbiA+PiBhID4+IGIgPj4gYzsKCQlhZGpNYXRbYV1bYl0gPSBjOwoJfQoJZm9yKGludCBpID0gMDsgaSA8IDY7IGkrKykgewoJCWZvcihpbnQgaiA9IDA7IGogPCA2OyBqKyspCgkJCXByaW50ZigiJTJkICIsIGFkak1hdFtpXVtqXSk7CgkJY291dCA8PCBlbmRsOwoJfQoJKi8KCS8vIEFkamFjZW5jeSBMaXN0CgkvLyBwcm86IHRlbmdhaDIgYW50YXJhIGFkaiBNYXRyaXggJiBFZGdlIGxpc3QKCS8vIGNvbjogLQoJLyoKCXZlY3RvcjxwYWlyPGludCwgaW50PiA+IGFkakxpc3RbNl07CgljaW4gPj4gZTsKCWZvcihpbnQgaSA9IDA7IGkgPCBlOyBpKyspIHsKCQlpbnQgYSwgYiwgYzsKCQljaW4gPj4gYSA+PiBiID4+IGM7CgkJYWRqTGlzdFthXS5wdXNoX2JhY2sobWFrZV9wYWlyKGIsIGMpKTsKCX0KCWZvcihpbnQgaSA9IDA7IGkgPCA2OyBpKyspIHsKCQljb3V0IDw8IGkgPDwgIjogIjsKCQlmb3IoaW50IGogPSAwOyBqIDwgYWRqTGlzdFtpXS5zaXplKCk7IGorKykKCQkJY291dCA8PCAiKCIgPDwgYWRqTGlzdFtpXVtqXS5maXJzdCA8PCAiLCAiCgkJCSAgICAgICAgICAgIDw8IGFkakxpc3RbaV1bal0uc2Vjb25kIDw8ICIpICI7CgkJY291dCA8PCBlbmRsOwoJfQoJKi8KCQoJLy8gT2JqZWN0LW9yaWVudGVkIHByb2dyYW1taW5nCgkKCS8vIEVkZ2UgTGlzdAoJLyoKCXZlY3RvcjxwYWlyPGludCwgcGFpcjxpbnQsIGludD4gPiA+IGVkZ2VMaXN0OwoJY2luID4+IGU7Cglmb3IoaW50IGkgPSAwOyBpIDwgZTsgaSsrKSB7CgkJaW50IGEsIGIsIGM7CgkJY2luID4+IGEgPj4gYiA+PiBjOwoJCWVkZ2VMaXN0LnB1c2hfYmFjayhtYWtlX3BhaXIoYywgbWFrZV9wYWlyKGEsIGIpKSk7Cgl9Cglzb3J0KGVkZ2VMaXN0LmJlZ2luKCksIGVkZ2VMaXN0LmVuZCgpKTsKCWZvcihpbnQgaSA9IDA7IGkgPCBlOyBpKyspCgkJY291dCA8PCAiKCIgPDwgZWRnZUxpc3RbaV0uc2Vjb25kLmZpcnN0IDw8ICIsICIKCQkgICAgICAgICAgICA8PCBlZGdlTGlzdFtpXS5zZWNvbmQuc2Vjb25kIDw8ICIpOiAiCgkJICAgICAgICAgICAgPDwgZWRnZUxpc3RbaV0uZmlyc3QgPDwgZW5kbDsKCSovCgkKCS8vIC0gR3JhcGggdHJhdmVyc2FsOiBEZXB0aC1GaXJzdCBTZWFyY2gKCS8qCgljaW4gPj4gbiA+PiBlOwoJZm9yKGludCBpID0gMDsgaSA8IGU7IGkrKykgewoJCWludCBhLCBiOwoJCWNpbiA+PiBhID4+IGI7CgkJYWRqTGlzdFthXS5wdXNoX2JhY2soYik7Cgl9CglpbnQgc3RhcnQgPSAxOwoJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKCQl2aXNpdGVkW2ldID0gZmFsc2U7CglkZnMoc3RhcnQpOwoJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKCQlpZih2aXNpdGVkW2ldKQoJCQljb3V0IDw8IGkgPDwgZW5kbDsKCSovCgkKCS8vIC0gRmxvb2QtZmlsbCBvbiBpbXBsaWNpdCBncmFwaAoJY2luID4+IFIgPj4gQzsKCWZvcihpbnQgaSA9IDA7IGkgPCBSOyBpKyspCgkJY2luID4+IGdyaWRbaV07CgljaGFyIGdhbnRpID0gJ2EnOwoJZm9yKGludCBpID0gMDsgaSA8IFI7IGkrKykKCQlmb3IoaW50IGogPSAwOyBqIDwgQzsgaisrKQoJCQlpZihncmlkW2ldW2pdID09ICcuJykgewoJCQkJZmYoaSwgaiwgZ2FudGkrKyk7CgkJCQlmb3IoaW50IGsgPSAwOyBrIDwgUjsgaysrKQoJCQkJCWNvdXQgPDwgZ3JpZFtrXSA8PCBlbmRsOwoJCQkJY291dCA8PCBlbmRsOwoJCQl9CgkKCS8qCgkjIyMjIyMjIyMjCgkjLi4jIy4uLi4jCgkjIyMjIy4uLi4jCgkjLi4uIyMjLi4jCgkjLi4uLi4jLi4jCgkjLi4uLiMjIyMjCgkjLi4uLiMuLi4jCgkjIyMjIyMjIyMjCgkgICAgdgoJIyMjIyMjIyMjIwoJIy4uIyMuLi4uIwoJIyMjIyMuLi4uIwoJI2FhYSMjIy4uIwoJI2FhYWFhIy4uIwoJI2FhYWEjIyMjIwoJI2FhYWEjLi4uIwoJIyMjIyMjIyMjIwoJCgkjIyMjIyMjIyMjCgkjLi4uLiMuLi4jCgkjLi4uLiMuIy4jCgkjIyMjIyMuIyMjCgkjLi4uLiMuLi4jCgkjLiMjIyMjIy4jCgkjLi4uLi4uLi4jCgkjIyMjIyMjIyMjCgkKCSovCgkKCXJldHVybiAwOwp9CgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKLy8gaHR0cHM6Ly9vLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5zLmNvbS9jb250ZXN0cy95aHgyeWI=