#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <fstream>
#include <cstdlib>
#include <vector>

using namespace std;

struct square {
    vector<square*> links;
    vector<square*> backLinks;
    char letter;
    int x, y;
    bool visited;
    square():visited(false){}
};

int height, width;

square* portalBegin[10] = {NULL};
square* portalEnd[10] = {NULL};

square* poi[5] = {NULL};

square **grid;

void explore(square* s) {
    if (s->visited) {
        return;
    }
    s->visited = true;
    for (int i = 0; i < s->links.size(); i++) {
        explore(s->links[i]);
    }
}

void clear() {
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            grid[y][x].visited = false;
        }
    }
}

int main() {
    ifstream inFile("DATA5.txt");
    ofstream outFile("OUT5.txt");
    
    inFile >> height >> width;
    
    grid = new square*[height];
    for (int y = 0; y < height; y++) {
        grid[y] = new square[width];
        for (int x = 0; x < width; x++) {
            char l;
            do {
                inFile.get(l);
            } while (l == '\n' || l == '\r' || l == ' ');
            grid[y][x].letter = l;
            grid[y][x].y = y;
            grid[y][x].x = x;
            if (l >= 'a' && l <= 'j') {
                portalBegin[l-'a'] = &grid[y][x];
            } else if (l >= 'A' && l <= 'J') {
                portalEnd[l-'A'] = &grid[y][x];
            }
            if (l >= '1' && l <= '5') {
                poi[l-'1'] = &grid[y][x];
            }
        }
    }
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if (y > 0 && grid[y-1][x].letter != '#') {
                grid[y][x].links.push_back(&grid[y-1][x]);
                grid[y-1][x].backLinks.push_back(&grid[y][x]);
            }
            if (y+1 < height && grid[y+1][x].letter != '#') {
                grid[y][x].links.push_back(&grid[y+1][x]);
                grid[y+1][x].backLinks.push_back(&grid[y][x]);
            }
            if (x > 0 && grid[y][x-1].letter != '#') {
                grid[y][x].links.push_back(&grid[y][x-1]);
                grid[y][x-1].backLinks.push_back(&grid[y][x]);
            }
            if (x+1 < width && grid[y][x+1].letter != '#') {
                grid[y][x].links.push_back(&grid[y][x+1]);
                grid[y][x+1].backLinks.push_back(&grid[y][x]);
            }
            if (grid[y][x].letter >= 'a' && grid[y][x].letter <= 'j') {
                grid[y][x].links.push_back(portalEnd[grid[y][x].letter - 'a']);
                printf("%p\n", portalEnd[grid[y][x].letter - 'a']);
                portalEnd[grid[y][x].letter - 'a']->backLinks.push_back(&grid[y][x]);
            }
        }
    }
    for (int i = 0; i < 5; i++) {
        clear();
        explore(poi[i]);
        outFile << i+1 << ':';
        bool first = true;
        for (int j = 0; j < 5; j++) {
            if (j == i) continue;
            if (poi[j]->visited) {
                if (!first) {
                    outFile << ' ';
                } else {
                    first = false;
                }
                outFile << j+1;
            }
        }
        outFile << endl;
    }
    
    system("pause");
    return 0;
}