407559: GYM102829 F The Great Shuffle

Back in the days when programming contests were held in person, team seating was often a great kerfuffle. Who will sit where? Is there enough room nearby for my entire team? Where is the nearest outlet? Can the opponents see my computer screen?!?

As competitors would sprawl out during the course of a contest in order to solve their problems, seat-hopping occurred practically every five minutes, and each competitor paid careful attention to precisely which chair she would try to move into, based on specific rules. Given a 2D map of the contest auditorium, with the locations of all chairs, competitors, and outlets, help simulate where the competitors of different teams will be located after a certain number of five-minute intervals!

Every five minutes, at the time of seat-hopping, each competitor will only attempt to move into an adjacent space in the contest auditorium if each of the following conditions is true...

1. If the space currently contains an empty chair, denoted '#'. This means that the space must not be empty without a chair, denoted by '.', and it must not have a chair with another competitor sitting on it, denoted by a lower-case letter uniquely identifying the team that that competitor belongs to.

2. If the chair is close enough to an outlet, denoted '*'. In order for a chair to be "close enough" to an outlet, the outlet must be within 3 cells of movement according to taxicab distance from the chair—meaning that, using only adjacent moves up/down/left/right through cells on the auditorium map, an outlet could be reached within 3 moves or less.

3. If the chair is not adjacent to where an opponent is sitting. If an opponent, meaning another competitor with a team name (denoted by a lower-case letter) different from this competitor's team name, is sitting adjacently to the empty chair, the competitor will not try to move into that chair because then their opponent might be able to steal answers!

4. If the space is the most preferred out of other viable, adjacent options. In the case where multiple adjacent chairs are eligible for the competitor to move into, according to the above rules, then the competitor will prefer to sit in the north adjacent chair first (above them on the map), then the chair to their west (left), then to their east (right), and lastly the southmost adjacent chair (below).

Once the competitor selects a viable adjacent chair to move into, if one exists, then at the time of seat-hopping, the competitor will try to move into the seat. However, if any other competitor (including one's team members) had a similar idea and is also trying to move into that same chair, both competitors will notice each other and decide to remain where they are currently seated, instead of race to the chair and fight over who gets to sit in it. It's simply common courtesy.

The first line of input will contain three space-separated integers: $$$N$$$ the number of rows in the auditorium map, $$$M$$$ the number of columns in the auditorium map, and $$$I$$$, the number of five-minute, seat-hopping intervals, where $$$1 \leq N, M, I \leq 100$$$. The next $$$N$$$ lines of input will each contain $$$M$$$ characters, where each character represents a cell in the auditorium as described above. There will be competitors from up to 26 different teams, and each team can have any number of competitors.

Print out the auditorium map with competitors relocated to where they would be sitting after $$$I$$$ iterations of seat-hopping. Don't forget that a chair will become vacant, denoted '#', each time a competitor leaves it.

7 29 1
.............................
..*......c...*.dd.....fff..*.
.###...b.c.....dd*.ee#fff**#.
.a*#...b.c**..dd#..ee##..***.
.*###..b*cc...***..*e#####...
.##.#a..*#*....##.*#e####g...
.............................

.............................
..*......c...*.dd.....fff..*.
.a##...b.c.....dd*.ee##ff**#.
.#*#...b.c**..dd#..e#ef..***.
.*###..b*#c...***..*#e###g...
.##.#a..*c*....##.*e######...
.............................