/*
╔══════════════════════════════════════════════════════════════════════════════╗
║ Instituição : Faculdade de Tecnologia de São Paulo ║
║ Departamento : Tecnologia da Informação ║
║ Curso : Análise e Desenvolvimento de Sistemas ║
║ Autor : Lucio Nunes de Lira ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ Competição : InterFatecs 2017 - Primeira fase ║
║ Programa : Problema F - Mário ║
║ Linguagem : ANSI C ║
║ Compilador : Pelles C (7.00.355) ║
║ Versão : A (Rev. 0) ║
╚══════════════════════════════════════════════════════════════════════════════╝
*/
#include <stdio.h>
#include <stdlib.h>
#define LIN 1002
#define COL 1002
typedef struct pos {
int lin, col, simb, vidas;
} Pos;
typedef Pos Item;
typedef struct fila {
int inicio, final, vagas, tam;
Item *itens;
} Fila;
int busca(char [][COL], int, int, int);
int cheia(Fila *);
int prox(int, Fila *);
int vazia(Fila *);
Item desenfileira(Fila *);
void posicao_mario(char [][COL], int, int, int *, int *) ;
void borda(char [][COL], int, int);
void cria(Fila *, int);
void enfileira(Item, Fila *);
void le_mapa(char [][COL], int, int);
int main(void) {
char mapa[LIN][COL];
int c, h, m_col, m_lin, w;
scanf("%d %d%*c", &h
, &w
); le_mapa(mapa, h, w);
borda(mapa, h, w);
posicao_mario(mapa, h, w, &m_lin, &m_col);
printf(busca
(mapa
, m_lin
, m_col
, c
* 4) ? "SIM\n" : "NAO\n"); return 0;
}
void posicao_mario(char mapa[][COL], int lin, int col, int *m_lin, int *m_col) {
int i, j;
for (i = 1; i <= lin; i++)
for (j = 1; j <= col; j++)
if (mapa[i][j] == 'S') {
*m_lin = i;
*m_col = j;
return;
}
}
void borda(char mapa[][COL], int lin, int col) {
int i;
for (i = 0; i <= lin + 1; i++) mapa[i][0] = mapa[i][col + 1] = 'x';
for (i = 1; i <= col ; i++) mapa[0][i] = mapa[lin + 1][i] = 'x';
}
void le_mapa(char mapa[][COL], int lin, int col) {
int i;
for (i
= 1; i
<= lin
; i
++) gets(mapa
[i
] + 1); }
void cria(Fila *f, int tam) {
f
->itens
= malloc(tam
* sizeof(Item
)); f->vagas = f->tam = tam;
f->inicio = f->final = 0;
}
int vazia(Fila *f) {
return f->vagas == f->tam;
}
int cheia(Fila *f) {
return f->vagas == 0;
}
void enfileira(Item x, Fila *f) {
if (cheia(f)) {
}
f->itens[f->final] = x;
f->vagas--;
f->final = prox(f->final, f);
}
Item desenfileira(Fila *f) {
if (vazia(f)) {
}
Item x = f->itens[f->inicio];
f->vagas++;
f->inicio = prox(f->inicio, f);
return x;
}
int prox(int pos, Fila *f) {
return (pos + 1) % f->tam;
}
int busca(char mapa[][COL], int lin, int col, int vidas) {
Fila f;
Pos p = {lin, col, mapa[lin][col], vidas};
cria(&f, LIN * COL);
enfileira(p, &f);
mapa[p.lin][p.col] = 'x';
while (!vazia(&f)) {
p = desenfileira(&f);
if (p.simb == 'T') return 1;
if (p.vidas == 0) continue;
if (mapa[p.lin-1][p.col] != 'x') {
enfileira((Pos){p.lin-1, p.col, mapa[p.lin-1][p.col], p.vidas-1}, &f);
mapa[p.lin-1][p.col] = 'x';
}
if (mapa[p.lin][p.col+1] != 'x') {
enfileira((Pos){p.lin, p.col+1, mapa[p.lin][p.col+1], p.vidas-1}, &f);
mapa[p.lin][p.col+1] = 'x';
}
if (mapa[p.lin+1][p.col] != 'x') {
enfileira((Pos){p.lin+1, p.col, mapa[p.lin+1][p.col], p.vidas-1}, &f);
mapa[p.lin+1][p.col] = 'x';
}
if (mapa[p.lin][p.col-1] != 'x') {
enfileira((Pos){p.lin, p.col-1, mapa[p.lin][p.col-1], p.vidas-1}, &f);
mapa[p.lin][p.col-1] = 'x';
}
}
return 0;
}
LyoK4pWU4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWXCuKVkSBJbnN0aXR1acOnw6NvICAgOiAgRmFjdWxkYWRlIGRlIFRlY25vbG9naWEgZGUgU8OjbyBQYXVsbyAgICAgICAgICAgICAgICAgICAgICAgIOKVkQrilZEgRGVwYXJ0YW1lbnRvICA6ICBUZWNub2xvZ2lhIGRhIEluZm9ybWHDp8OjbyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIOKVkQrilZEgQ3Vyc28gICAgICAgICA6ICBBbsOhbGlzZSBlIERlc2Vudm9sdmltZW50byBkZSBTaXN0ZW1hcyAgICAgICAgICAgICAgICAgICAgICAg4pWRCuKVkSBBdXRvciAgICAgICAgIDogIEx1Y2lvIE51bmVzIGRlIExpcmEgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIOKVkQrilaDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilaMK4pWRIENvbXBldGnDp8OjbyAgICA6ICBJbnRlckZhdGVjcyAyMDE3IC0gUHJpbWVpcmEgZmFzZSAgICAgICAgICAgICAgICAgICAgICAgICAgICDilZEK4pWRIFByb2dyYW1hICAgICAgOiAgUHJvYmxlbWEgRiAtIE3DoXJpbyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIOKVkQrilZEgTGluZ3VhZ2VtICAgICA6ICBBTlNJIEMgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICDilZEK4pWRIENvbXBpbGFkb3IgICAgOiAgUGVsbGVzIEMgKDcuMDAuMzU1KSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg4pWRCuKVkSBWZXJzw6NvICAgICAgICA6ICBBIChSZXYuIDApICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICDilZEK4pWa4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWdCiovCgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgoKI2RlZmluZSBMSU4gMTAwMgojZGVmaW5lIENPTCAxMDAyCgp0eXBlZGVmIHN0cnVjdCBwb3MgewogICAgICAgICAgICBpbnQgbGluLCBjb2wsIHNpbWIsIHZpZGFzOwogICAgICAgIH0gUG9zOwoKdHlwZWRlZiBQb3MgSXRlbTsKCnR5cGVkZWYgc3RydWN0IGZpbGEgewogICAgICAgICAgICBpbnQgaW5pY2lvLCBmaW5hbCwgdmFnYXMsIHRhbTsKICAgICAgICAgICAgSXRlbSAqaXRlbnM7CiAgICAgICAgfSBGaWxhOwoKaW50IGJ1c2NhKGNoYXIgW11bQ09MXSwgaW50LCBpbnQsIGludCk7CmludCBjaGVpYShGaWxhICopOwppbnQgcHJveChpbnQsIEZpbGEgKik7CmludCB2YXppYShGaWxhICopOwpJdGVtIGRlc2VuZmlsZWlyYShGaWxhICopOwp2b2lkIHBvc2ljYW9fbWFyaW8oY2hhciBbXVtDT0xdLCBpbnQsIGludCwgaW50ICosIGludCAqKSA7CnZvaWQgYm9yZGEoY2hhciBbXVtDT0xdLCBpbnQsIGludCk7CnZvaWQgY3JpYShGaWxhICosIGludCk7CnZvaWQgZW5maWxlaXJhKEl0ZW0sIEZpbGEgKik7CnZvaWQgbGVfbWFwYShjaGFyIFtdW0NPTF0sIGludCwgaW50KTsKCmludCBtYWluKHZvaWQpIHsKICAgIGNoYXIgbWFwYVtMSU5dW0NPTF07CiAgICBpbnQgYywgaCwgbV9jb2wsIG1fbGluLCB3OwogICAgc2NhbmYoIiVkICVkJSpjIiwgJmgsICZ3KTsKICAgIGxlX21hcGEobWFwYSwgaCwgdyk7CiAgICBzY2FuZigiJWQlKmMiLCAmYyk7Cglib3JkYShtYXBhLCBoLCB3KTsKCXBvc2ljYW9fbWFyaW8obWFwYSwgaCwgdywgJm1fbGluLCAmbV9jb2wpOwogICAgcHJpbnRmKGJ1c2NhKG1hcGEsIG1fbGluLCBtX2NvbCwgYyAqIDQpID8gIlNJTVxuIiA6ICJOQU9cbiIpOwogICAgcmV0dXJuIDA7Cn0KCnZvaWQgcG9zaWNhb19tYXJpbyhjaGFyIG1hcGFbXVtDT0xdLCBpbnQgbGluLCBpbnQgY29sLCBpbnQgKm1fbGluLCBpbnQgKm1fY29sKSB7CglpbnQgaSwgajsKCglmb3IgKGkgPSAxOyBpIDw9IGxpbjsgaSsrKQoJCWZvciAoaiA9IDE7IGogPD0gY29sOyBqKyspCgkJCWlmIChtYXBhW2ldW2pdID09ICdTJykgewoJCQkJKm1fbGluID0gaTsKCQkJCSptX2NvbCA9IGo7CgkJCQlyZXR1cm47CgkJCX0KfQoKdm9pZCBib3JkYShjaGFyIG1hcGFbXVtDT0xdLCBpbnQgbGluLCBpbnQgY29sKSB7CiAgICBpbnQgaTsKICAgIGZvciAoaSA9IDA7IGkgPD0gbGluICsgMTsgaSsrKSBtYXBhW2ldWzBdID0gbWFwYVtpXVtjb2wgKyAxXSA9ICd4JzsKICAgIGZvciAoaSA9IDE7IGkgPD0gY29sICAgIDsgaSsrKSBtYXBhWzBdW2ldID0gbWFwYVtsaW4gKyAxXVtpXSA9ICd4JzsKfQoKdm9pZCBsZV9tYXBhKGNoYXIgbWFwYVtdW0NPTF0sIGludCBsaW4sIGludCBjb2wpIHsKICAgIGludCBpOwogICAgZm9yIChpID0gMTsgaSA8PSBsaW47IGkrKykgZ2V0cyhtYXBhW2ldICsgMSk7Cn0KCnZvaWQgY3JpYShGaWxhICpmLCBpbnQgdGFtKSB7CiAgICBmLT5pdGVucyA9IG1hbGxvYyh0YW0gKiBzaXplb2YoSXRlbSkpOwogICAgZi0+dmFnYXMgPSBmLT50YW0gPSB0YW07CiAgICBmLT5pbmljaW8gPSBmLT5maW5hbCA9IDA7Cn0KCmludCB2YXppYShGaWxhICpmKSB7CiAgICByZXR1cm4gZi0+dmFnYXMgPT0gZi0+dGFtOwp9CgppbnQgY2hlaWEoRmlsYSAqZikgewogICAgcmV0dXJuIGYtPnZhZ2FzID09IDA7Cn0KCnZvaWQgZW5maWxlaXJhKEl0ZW0geCwgRmlsYSAqZikgewogICAgaWYgKGNoZWlhKGYpKSB7CiAgICAgICAgcHJpbnRmKCJlcnJvOiBmaWxhIGNoZWlhIik7CiAgICAgICAgYWJvcnQoKTsKICAgIH0KICAgIGYtPml0ZW5zW2YtPmZpbmFsXSA9IHg7CiAgICBmLT52YWdhcy0tOwogICAgZi0+ZmluYWwgPSBwcm94KGYtPmZpbmFsLCBmKTsKfQoKSXRlbSBkZXNlbmZpbGVpcmEoRmlsYSAqZikgewogICAgaWYgKHZhemlhKGYpKSB7CiAgICAgICAgcHJpbnRmKCJlcnJvOiBmaWxhIHZhemlhIik7CiAgICAgICAgYWJvcnQoKTsKICAgIH0KICAgIEl0ZW0geCA9IGYtPml0ZW5zW2YtPmluaWNpb107CiAgICBmLT52YWdhcysrOwogICAgZi0+aW5pY2lvID0gcHJveChmLT5pbmljaW8sIGYpOwogICAgcmV0dXJuIHg7Cn0KCmludCBwcm94KGludCBwb3MsIEZpbGEgKmYpIHsKICAgIHJldHVybiAocG9zICsgMSkgJSBmLT50YW07Cn0KCmludCBidXNjYShjaGFyIG1hcGFbXVtDT0xdLCBpbnQgbGluLCBpbnQgY29sLCBpbnQgdmlkYXMpIHsKICAgIEZpbGEgZjsKICAgIFBvcyBwID0ge2xpbiwgY29sLCBtYXBhW2xpbl1bY29sXSwgdmlkYXN9OwoKICAgIGNyaWEoJmYsIExJTiAqIENPTCk7CiAgICBlbmZpbGVpcmEocCwgJmYpOwogICAgbWFwYVtwLmxpbl1bcC5jb2xdID0gJ3gnOwoKICAgIHdoaWxlICghdmF6aWEoJmYpKSB7CiAgICAgICAgcCA9IGRlc2VuZmlsZWlyYSgmZik7CiAgICAgICAgaWYgKHAuc2ltYiA9PSAnVCcpIHJldHVybiAxOwogICAgICAgIGlmIChwLnZpZGFzID09IDApIGNvbnRpbnVlOwoKICAgICAgICBpZiAobWFwYVtwLmxpbi0xXVtwLmNvbF0gIT0gJ3gnKSB7CiAgICAgICAgICAgIGVuZmlsZWlyYSgoUG9zKXtwLmxpbi0xLCBwLmNvbCwgbWFwYVtwLmxpbi0xXVtwLmNvbF0sIHAudmlkYXMtMX0sICZmKTsKICAgICAgICAgICAgbWFwYVtwLmxpbi0xXVtwLmNvbF0gPSAneCc7CiAgICAgICAgfQoKICAgICAgICBpZiAobWFwYVtwLmxpbl1bcC5jb2wrMV0gIT0gJ3gnKSB7CiAgICAgICAgICAgIGVuZmlsZWlyYSgoUG9zKXtwLmxpbiwgcC5jb2wrMSwgbWFwYVtwLmxpbl1bcC5jb2wrMV0sIHAudmlkYXMtMX0sICZmKTsKICAgICAgICAgICAgbWFwYVtwLmxpbl1bcC5jb2wrMV0gPSAneCc7CiAgICAgICAgfQoKICAgICAgICBpZiAobWFwYVtwLmxpbisxXVtwLmNvbF0gIT0gJ3gnKSB7CiAgICAgICAgICAgIGVuZmlsZWlyYSgoUG9zKXtwLmxpbisxLCBwLmNvbCwgbWFwYVtwLmxpbisxXVtwLmNvbF0sIHAudmlkYXMtMX0sICZmKTsKICAgICAgICAgICAgbWFwYVtwLmxpbisxXVtwLmNvbF0gPSAneCc7CiAgICAgICAgfQoKICAgICAgICBpZiAobWFwYVtwLmxpbl1bcC5jb2wtMV0gIT0gJ3gnKSB7CiAgICAgICAgICAgIGVuZmlsZWlyYSgoUG9zKXtwLmxpbiwgcC5jb2wtMSwgbWFwYVtwLmxpbl1bcC5jb2wtMV0sIHAudmlkYXMtMX0sICZmKTsKICAgICAgICAgICAgbWFwYVtwLmxpbl1bcC5jb2wtMV0gPSAneCc7CiAgICAgICAgfQogICAgfQoKICAgIHJldHVybiAwOwp9Cg==