Problema C - Roboterapia

Num momento de aborrecimento, decidiste aventurar-te na programação e na robótica, e construíste um robot, Oliver.

O Oliver pode mover-se em quatro direcções: cima, baixo, esquerda e direita. Para que ele se possa movimentar, terás que lhe fornecer uma sequência de instruções D (down/baixo), R (right/direita), U (up/cima) e L (left/esquerda), por exemplo DDRRURRDD. O Oliver executa cada instrução uma a uma.

Contudo, tal como em todos os filmes de ficção científica com robots, apercebeste-te que o Oliver foi capaz de ganhar vontade própria. Após alguma análise, descobriste que, com 25% de probabilidade, ele faz o movimento oposto ao que lhe deste como instrução. Por exemplo, se lhe forneceste a instrução R, ele executou a instrução L.

Numa tentativa de ganhares de novo controlo sobre o Oliver, e para fazer aquilo a que chamaste de roboterapia, preparaste uma série de grelhas, N por N, onde cada célula pode ser livre ou bloqueada. O Oliver não se pode mover para uma célula bloqueada e quando recebe uma instrução que o faça mover-se para uma (seja por seguir ou desobedecer a instrução), ignora esta instrução e passa à próxima.

O objetivo é o Oliver começar na célula (1,1) e chegar à célula (N, N). Para este efeito, as células (1,1) e (N,N) estão sempre livres e há pelo menos um caminho de (1,1) para (N,N). Além disso, a grelha está rodeada por células bloqueadas, o que significa que, por exemplo, não é possível mover-se para cima ou para a esquerda da célula (1,1).

Um exemplo de uma grelha com N = 5 (S designa a célula (1,1) e F a célula (5,5)):

S####
.#...
...#.
.###.
.###F

As células com . são livres e as células com # estão bloqueadas. Para este exemplo, se o Oliver executasse as instruções DDRRURRDDD sem desobedecer a nenhuma, então chegaria à posição objetivo.

A tua tarefa é indicares um conjunto de no máximo 200N instruções para cada uma das grelhas, no formato especificado anterior, de forma a que quando o Oliver as executa a probabilidade de chegar com sucesso à célula (N, N) é de pelo menos 80%. Nota que o Oliver não tem de executar todas as suas instruções e terminar na célula (N,N). Assim que se encontrar na célula (N,N), o objetivo foi sucedido, mesmo que ainda haja mais instruções para executar. Se após executar todas as instruções Oliver não tiver chegado à célula (N,N), então o objetivo foi falhado.

O Problema

Serão fornecidas 5 grelhas como a descrita acima, o objetivo é construir uma sequência de no máximo 200N instruções D, R, U, L, de forma a que o robot partindo da célula (1,1) chegue à célula (N,N) com probabilidade pelo menos 80%.

Input

Cada caso de teste começa com um inteiro N, representando o tamanho da grelha.

Seguem-se N linhas, cada uma com N caracteres que representam a grelha. Um carácter . representa uma célula livre, um carácter # representa uma célula bloqueada.

Casos de teste

Há 5 casos de teste, cada um a valer 20 pontos (sem pontuações parciais para cada um). Devem olhar para cada caso de teste individualmente, os casos não são aleatórios e devem observar e aproveitar a estrutura de cada um para o resolver.

Para cada caso de teste o cálculo da percentagem de sucesso é feita da seguinte forma: serão feitas 1000 simulações aleatórias (usando as instruções fornecidas), se pelo menos 800 forem sucedidas, então o caso de teste é considerado correcto.

Os casos de teste são os seguintes:

• Caso 1: N = 5, grelha pequena (é o exemplo dado no enunciado), inp1.txt;
• Caso 2: N = 25, um só caminho entre (1, 1) e (N, N), inp2.txt;
• Caso 3: N = 50, todas as células são livres, inp3.txt;
• Caso 4: N = 50, um caminho único com um beco sem saída, inp4.txt;
• Caso 5: N = 50, cada célula é bloqueada com probabilidade uniforme e independente de 30%, inp5.txt.

Output/Submissão

Deve ser submetido um único ficheiro de txt (o formato é importante, o vosso ficheiro deve terminar em .txt) com as strings pretendidas para cada caso de teste, sendo que o formato é o seguinte:

M₁ (número de instruções para o caso de teste 1)
I1 I2...IM₁ (string de tamanho M₁ que representa as instruções para o caso de teste 1)
M₂ (número de instruções para o caso de teste 2)
I1 I2...IM₂ (string de tamanho M₂ que representa as instruções para o caso de teste 2)
M₃ (número de instruções para o caso de teste 3)
I1 I2...IM₃ (string de tamanho M₃ que representa as instruções para o caso de teste 3)
M₄ (número de instruções para o caso de teste 4)
I1 I2...IM₄ (string de tamanho M₄ que representa as instruções para o caso de teste 4)
M₅ (número de instruções para o caso de teste 5)
I1 I2...IM₅ (string de tamanho M₅ que representa as instruções para o caso de teste 5)

Observações importantes:

• Cada Ii representa uma instrução (que, tal como descrito no enunciado, pode ser D, R, U e L).
• Não devem incluir espaços entre os caracteres das instruções.
• Caso não tenham solução para um dos casos de teste, basta colocarem M_i = 0, ou seja, imprimir 0 seguido de uma linha vazia para representar a resposta a este caso de teste.
• Se algum dos outputs for inválido, seja porque M_i é menor que 0 ou maior que 200N (para a grelha do caso de teste correspondente), ou porque o número de caracteres que representam instruções for diferente de M_i, ou porque as instruções não usam apenas os caracteres D, R, U, L, o resultado da submissão será Wrong Answer e terão 0 pontos.
• A pontuação de uma submissão é igual a 20 vezes o número de casos de teste para os quais as instruções que indicaram obtêm sucesso com 80% de probabilidade (dada a simulação mencionada acima).

Um exemplo válido de um ficheiro solução seria o seguinte (a sua pontuação é de 0 pontos):

4
LRUD
2
LU
0

1
D
0

Dicas para gerar o output

Visto que é necessário criar um ficheiro de txt para a vossa submissão, pode ser útil usar o terminal para gerar os ficheiros de texto (isto não é obrigatório, podem criar o ficheiro como quiserem).

Se para correrem o vosso programa usarem o comando X (por exemplo, para C++ isto seria algo como ./a.out, depois de compilar com g++ codigo.cpp), podem usar o seguinte comando para ler o input de um ficheiro inp.txt e escrever para um ficheiro out.txt: X < inp.txt > out.txt.

Para facilitar a organização do ficheiro de submissão, é aconselhado gerar um txt por cada caso de teste, por exemplo, para o caso de teste 2 ter um out2.txt, que teria o formato:

M₂ (número de instruções para o caso de teste 2)

I1 I2...IM₂ (string de tamanho M₂ que representa as instruções para o caso de teste 2)

Para posteriormente gerar um ficheiro out.txt para submeter, podem usar o seguinte comando (assumindo que têm um ficheiro outI.txt para cada um dos 5 casos de teste I): cat out1.txt > out.txt;cat out2.txt >> out.txt;cat out3.txt >> out.txt;cat out4.txt >> out.txt;cat out5.txt >> out.txt

Simulador

Para poderem estimar a qualidade dos conjuntos de instruções que criarem podem usar o seguinte código em C++ que simula o comportamento do robot e calcula uma percentagem de sucesso:

• simulador.cpp

Devem compilar o código do simulador da seguinte forma:

• g++ simulador.cpp -std=c++11 -O2 -Wno-unused-result -o simulador

Devem correr o simulador da seguinte forma:

• ./simulador inp1.txt out1.txt

Onde inp1.txt deve corresponder ao ficheiro de input que quiserem testar e out1.txt à vossa solução descrita nos moldes mencionados anteriormente (deve apenas conter a solução para o input fornecido). Notem que a ordem dos ficheiros é importante.

Notem que este simulador não é o mesmo usado pelo grader no Mooshak. É possível terem uma percentagem de sucesso superior a 80% neste grader, mas inferior no usado pelo Mooshak (e vice-versa).