URI PROBLEMA 1057 - Chegando Junto SOLUÇÃO EM C++

Você está jogando um jogo de computador no qual três robôs (Aneed, Ben e Cindy) estão presos em um labirinto. Inicialmente todos os três estão situados em três localizações diferentes no labirinto. Existem três saídas através das quais os robôs têm que sair. Como esperado, há vários obstáculos no labirinto e os robôs não podem passar por eles.

O labirinto pode ser modelado como uma grade quadrada, com células NxN. Os robôs são colocados em três diferentes células no labirinto. Você pode comandá-los a se mover. Um único comando será ativado para os três robôs simultaneamente. Um robô irá mover-se para uma nova posição se for uma célula vazia dentro do labirinto ou se for uma das células alvo. Caso contrário, o comando será ignorado para aquele robô. A sua tarefa é comandá-los de forma que todos eles cheguem nas três células alvo (em qualquer ordem).

Cada movimento leva 1 unidade de tempo e consiste em:
Move North - O robô se move uma célula para o norte.
Move East - O robô se move uma célula para o leste.
Move South - O robô se move uma célula para o sul.
Move West - O robô se move uma célula para o oeste.

Cada célula consiste em um dos seguintes caracteres:
A – Posição Inicial de Aneed
B – Posição Inicial de Ben
C – Posição Inicial de Cindy
. – Célula vazia
# - Obstáculo
X – Célula alvo

Assuma que para todo labirinto cada uma das três letras (A B C) aparecerá exatamente uma vez e cada X aparecerá 3 vezes.

Entrada

A primeira linha de entrada é um inteiro T (T < 50), que indica o número de casos de testes. Cada caso inicia com um inteiro N (2 < N < 10). Cada uma das próximas N linhas contém N caracteres cada que preencherão o labirinto.

Saída

Para cada caso, imprima o número do caso seguido do menor tempo requerido. Se for impossível movê-los como descrito, imprima ‘trapped’ ao invés de imprimir o tempo. Note que o primeiro caso de teste corresponde à figura acima.

#include <cstdio>

#include <queue>

#define MAXN 9

using namespace std;

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

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

struct ponto{

int x1,y1,x2,y2,x3,y3,percorrido;

ponto(int _x1,int _y1,int _x2,int _y2,int _x3,int _y3,int _percorrido) : x1(_x1),y1(_y1),x2(_x2),y2(_y2),x3(_x3),y3(_y3),percorrido(_percorrido) {};

};

int matriz[MAXN][MAXN][MAXN][MAXN][MAXN][MAXN],n;

char mapa[MAXN][MAXN];

inline int cord(int x, int y){

if(x >= n) return 0;

if(y >= n) return 0;

if(x < 0) return 0;

if(y < 0) return 0;

return 1;

}

inline int valido(ponto d){

if(d.x1 == d.x2 && d.y1 == d.y2) return 0;

if(d.x1 == d.x3 && d.y1 == d.y3) return 0;

if(d.x2 == d.x3 && d.y2 == d.y3) return 0;

return 1;

}

int main(){

int TC;

scanf("%d",&TC);

for(int tc = 1;tc<=TC;tc++){

scanf("%d",&n);

int possivel = 0;

for(int i1=0;i1<n;i1++){

for(int i2=0;i2<n;i2++){

for(int i3=0;i3<n;i3++){

for(int i4=0;i4<n;i4++){

for(int i5=0;i5<n;i5++){

for(int i6=0;i6<n;i6++){

matriz[i1][i2][i3][i4][i5][i6] = 0;

}

int x1,y1,x2,y2,x3,y3;

for(int i=0;i<n;i++){

scanf("%s",mapa[i]);

for(int j=0;j<n;j++){

if(mapa[i][j] == 'A'){

x1 = i;

y1 = j;

}

if(mapa[i][j] == 'B'){

x2 = i;

y2 = j;

}

if(mapa[i][j] == 'C'){

x3 = i;

y3 = j;

}

ponto ini(x1,y1,x2,y2,x3,y3,0);

queue<ponto> bfs;

bfs.push(ini);

while(!bfs.empty()){

ponto d = bfs.front();

bfs.pop();

//printf("%d %d %d %d %d %d\n",d.x1,d.y1,d.x2,d.y2,d.x3,d.y3);

if(mapa[d.x1][d.y1] == 'X' && mapa[d.x2][d.y2] == 'X' && mapa[d.x3][d.y3] == 'X'){

possivel = 1;

printf("Case %d: %d\n",tc,d.percorrido);

break;

}

if(matriz[d.x1][d.y1][d.x2][d.y2][d.x3][d.y3]) continue;

matriz[d.x1][d.y1][d.x2][d.y2][d.x3][d.y3] = 1;

for(int i=0;i<4;i++){

ponto agora(d.x1 + (cord(d.x1 + dx[i],d.y1 + dy[i]) && mapa[d.x1+dx[i]][d.y1] != '#' ? dx[i] : 0),d.y1 + (cord(d.x1 + dx[i],d.y1 + dy[i]) && mapa[d.x1][d.y1+dy[i]] != '#' ? dy[i] : 0),d.x2 + (cord(d.x2 + dx[i], d.y2 + dy[i]) && mapa[d.x2+dx[i]][d.y2] != '#' ? dx[i] : 0),d.y2 + (cord(d.x2 + dx[i], d.y2 + dy[i]) && mapa[d.x2][d.y2+dy[i]] != '#' ? dy[i] : 0),d.x3 + (cord(d.x3 + dx[i],d.y3 + dy[i]) && mapa[d.x3+dx[i]][d.y3] != '#' ? dx[i] : 0), d.y3 + (cord(d.x3 + dx[i],d.y3 + dy[i]) && mapa[d.x3][d.y3+dy[i]] != '#' ? dy[i] : 0), d.percorrido+1);