fork download
copy 
  1. /*
  2. ╔══════════════════════════════════════════════════════════════════════════════╗
  3. ║ Instituição   :  Faculdade de Tecnologia de São Paulo                        ║
  4. ║ Departamento  :  Tecnologia da Informação                                    ║
  5. ║ Curso         :  Análise e Desenvolvimento de Sistemas                       ║
  6. ║ Autor         :  Lucio Nunes de Lira                                         ║
  7. ╠══════════════════════════════════════════════════════════════════════════════╣
  8. ║ Competição    :  InterFatecs 2017 - Primeira fase                            ║
  9. ║ Programa      :  Problema F - Mário                                          ║
  10. ║ Linguagem     :  ANSI C                                                      ║
  11. ║ Compilador    :  Pelles C (7.00.355)                                         ║
  12. ║ Versão        :  A (Rev. 0)                                                  ║
  13. ╚══════════════════════════════════════════════════════════════════════════════╝
  14. */
  15.  
  16. #include <stdio.h>
  17. #include <stdlib.h>
  18.  
  19. #define LIN 1002
  20. #define COL 1002
  21.  
  22. typedef struct pos {
  23.             int lin, col, simb, vidas;
  24.         } Pos;
  25.  
  26. typedef Pos Item;
  27.  
  28. typedef struct fila {
  29.             int inicio, final, vagas, tam;
  30.             Item *itens;
  31.         } Fila;
  32.  
  33. int busca(char [][COL], int, int, int);
  34. int cheia(Fila *);
  35. int prox(int, Fila *);
  36. int vazia(Fila *);
  37. Item desenfileira(Fila *);
  38. void posicao_mario(char [][COL], int, int, int *, int *) ;
  39. void borda(char [][COL], int, int);
  40. void cria(Fila *, int);
  41. void enfileira(Item, Fila *);
  42. void le_mapa(char [][COL], int, int);
  43.  
  44. int main(void) {
  45.     char mapa[LIN][COL];
  46.     int c, h, m_col, m_lin, w;
  47.     scanf("%d %d%*c", &h, &w);
  48.     le_mapa(mapa, h, w);
  49.     scanf("%d%*c", &c);
  50. 	borda(mapa, h, w);
  51. 	posicao_mario(mapa, h, w, &m_lin, &m_col);
  52.     printf(busca(mapa, m_lin, m_col, c * 4) ? "SIM\n" : "NAO\n");
  53.     return 0;
  54. }
  55.  
  56. void posicao_mario(char mapa[][COL], int lin, int col, int *m_lin, int *m_col) {
  57. 	int i, j;
  58.  
  59. 	for (i = 1; i <= lin; i++)
  60. 		for (j = 1; j <= col; j++)
  61. 			if (mapa[i][j] == 'S') {
  62. 				*m_lin = i;
  63. 				*m_col = j;
  64. 				return;
  65. 			}
  66. }
  67.  
  68. void borda(char mapa[][COL], int lin, int col) {
  69.     int i;
  70.     for (i = 0; i <= lin + 1; i++) mapa[i][0] = mapa[i][col + 1] = 'x';
  71.     for (i = 1; i <= col    ; i++) mapa[0][i] = mapa[lin + 1][i] = 'x';
  72. }
  73.  
  74. void le_mapa(char mapa[][COL], int lin, int col) {
  75.     int i;
  76.     for (i = 1; i <= lin; i++) gets(mapa[i] + 1);
  77. }
  78.  
  79. void cria(Fila *f, int tam) {
  80.     f->itens = malloc(tam * sizeof(Item));
  81.     f->vagas = f->tam = tam;
  82.     f->inicio = f->final = 0;
  83. }
  84.  
  85. int vazia(Fila *f) {
  86.     return f->vagas == f->tam;
  87. }
  88.  
  89. int cheia(Fila *f) {
  90.     return f->vagas == 0;
  91. }
  92.  
  93. void enfileira(Item x, Fila *f) {
  94.     if (cheia(f)) {
  95.         printf("erro: fila cheia");
  96.         abort();
  97.     }
  98.     f->itens[f->final] = x;
  99.     f->vagas--;
  100.     f->final = prox(f->final, f);
  101. }
  102.  
  103. Item desenfileira(Fila *f) {
  104.     if (vazia(f)) {
  105.         printf("erro: fila vazia");
  106.         abort();
  107.     }
  108.     Item x = f->itens[f->inicio];
  109.     f->vagas++;
  110.     f->inicio = prox(f->inicio, f);
  111.     return x;
  112. }
  113.  
  114. int prox(int pos, Fila *f) {
  115.     return (pos + 1) % f->tam;
  116. }
  117.  
  118. int busca(char mapa[][COL], int lin, int col, int vidas) {
  119.     Fila f;
  120.     Pos p = {lin, col, mapa[lin][col], vidas};
  121.  
  122.     cria(&f, LIN * COL);
  123.     enfileira(p, &f);
  124.     mapa[p.lin][p.col] = 'x';
  125.  
  126.     while (!vazia(&f)) {
  127.         p = desenfileira(&f);
  128.         if (p.simb == 'T') return 1;
  129.         if (p.vidas == 0) continue;
  130.  
  131.         if (mapa[p.lin-1][p.col] != 'x') {
  132.             enfileira((Pos){p.lin-1, p.col, mapa[p.lin-1][p.col], p.vidas-1}, &f);
  133.             mapa[p.lin-1][p.col] = 'x';
  134.         }
  135.  
  136.         if (mapa[p.lin][p.col+1] != 'x') {
  137.             enfileira((Pos){p.lin, p.col+1, mapa[p.lin][p.col+1], p.vidas-1}, &f);
  138.             mapa[p.lin][p.col+1] = 'x';
  139.         }
  140.  
  141.         if (mapa[p.lin+1][p.col] != 'x') {
  142.             enfileira((Pos){p.lin+1, p.col, mapa[p.lin+1][p.col], p.vidas-1}, &f);
  143.             mapa[p.lin+1][p.col] = 'x';
  144.         }
  145.  
  146.         if (mapa[p.lin][p.col-1] != 'x') {
  147.             enfileira((Pos){p.lin, p.col-1, mapa[p.lin][p.col-1], p.vidas-1}, &f);
  148.             mapa[p.lin][p.col-1] = 'x';
  149.         }
  150.     }
  151.  
  152.     return 0;
  153. }
  154.  
Success #stdin #stdout 0s 25984KB
comments (?)
stdin
copy 
1 6
.S...T
1
stdout
copy 
SIM
https://ideone.com/x0am7U
language:
C (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!