
\documentclass[10pt]{report}
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\setlength{\parskip}{0.5pc}
\setlength{\parindent}{0pt}

\setlength{\textwidth}{38pc}
\setlength{\textheight}{26cm}
\setlength{\topmargin}{-2cm}
\setlength{\oddsidemargin}{0.5cm}

\setlength{\evensidemargin}{0.5cm}  
\setlength{\baselineskip}{10pc}
\begin{document}

\newcommand{\novalinha}{\par \bigskip}
\newcommand{\bx}{\begin{flushright}\vspace{-0.7cm}$_\Box$\end{flushright}\par}

\newtheorem{fig}{Figura}[chapter]
\newtheorem{tb}{Tabela}[chapter]
\newtheorem{df}{\hspace{0.5cm} Definição}[chapter]
\newtheorem{lema}{\hspace{0.5cm} Lema}[chapter]


\def\ni{\noindent}
\def\ida{\makebox[0.5cm]{}}
\def\idab{\makebox[0.75cm]{}}
\def\idb{\makebox[1.05cm]{}}
\def\idc{\makebox[1.5cm]{}}
\def\idcd{\makebox[1.75cm]{}}
\def\idd{\makebox[2cm]{}}
\def\idde{\makebox[2.25cm]{}}
\def\ide{\makebox[2.5cm]{}}
\def\idf{\makebox[3.0cm]{}}

\def\ua{\uparrow}


\def\pule{\vspace{0.2cm}}
\def\pulao{\vspace{0.5cm}}
\def\pulaozao{\vspace{1cm}}

%
%-----------------------------------------------------------------

\hfill {\small Departamento de Ciência da Computação -- IME-USP}

\begin{center}
  \textbf{\large MAC 115 -- Introdução à Computação para Ciências Exatas e
    Tecnologia}
  
  \textsc{Instituto de Física  -- Segundo Semestre de 2001 -  Bacharelado Noturno}
\end{center}

\noindent
Terceiro Exercício-Programa (EP3)\hfill Prazo de entrega: 29 de novembro de 2001

\begin{center}
  \underline{\Large Alagações na USSP}
\end{center}

\noindent 

Devido a um forte temporal que caiu em São Paulo, várias regiões da
cidade universitária da USSP (Universidade de Sábios Samaritanos
Pragmáticos) ficaram alagadas.  Representamos o {\it campus} da USSP
por um reticulado, como o da figura abaixo, onde {$0$} representa uma
posição {\bf seca} e {$-1$} representa uma posição {\bf alagada}.

\begin{center}

\begin{tabular}{|r|r|r|r|r|r|r|r|r|r|} \hline
$-1$&0&0&0&0&$-1$&$-1$&0&$-1$&$-1$\\ \hline
$-1$&$-1$&$-1$&0&0&0&$-1$&0&$-1$&0\\ \hline
0&$-1$&0&0&$-1$&0&0&0&0&0\\ \hline
0&0&0&$-1$&$-1$&$-1$&$-1$&$-1$&0&0\\ \hline
0&0&0&0&$-1$&$-1$&0&0&$-1$&$-1$\\ \hline
0&0&$-1$&0&0&0&0&$-1$&$-1$&$-1$\\ \hline 
0&0&$-1$&$-1$&$-1$&0&0&0&$-1$&$-1$\\ \hline
$-1$&0&$-1$&$-1$&$-1$&$-1$&0&0&0&$-1$\\ \hline
$-1$&0&0&0&0&0&$-1$&$-1$&0&0\\ \hline
$-1$&0&0&0&0&0&$-1$&0&0&0\\ \hline
\end{tabular}

\end{center}

Dizemos que duas posições deste reticulado são {\bf adjacentes} se
possuem uma aresta em comum. Uma {\bf região} {\bf R} é definida como
um conjunto de posições tal que é possível a partir de uma posição de
{\bf R}, atingir qualquer outra posição de {\bf R} através de posições
adjacentes. Se todas as posições de uma região contêm $-1$ então a
região é dita {\bf alagada}.  Uma {\bf região alagada maximal} é
uma região alagada que não está contida em nenhuma região alagada a não ser
ela mesma.

    
\section*{Exercício-programa}


Faça um programa em C que resolva o seguinte problema: dado um
reticulado do tipo acima (uma matriz), marcar todas as regiões
alagadas maximais.  Especificações a serem seguidas:


\begin{enumerate}
  
\item Dados: dois inteiros $m$ e $n$ e $U_{m \times n}$ uma matriz
  inteira representando um reticulado com entradas $0$ e $-1$. (Na
  figura acima temos $m=n=10$.)
  
\item A partir da matriz $U$ construir uma nova matriz $M$ (de mesma
  dimensão) marcando cada {\bf região alagada maximal} com um número
  inteiro, da seguinte forma: Se existirem $k$ regiões alagadas
  maximais então cada posição de uma mesma região recebe um número
  entre 1 a $k$, sendo que todas as posições de uma mesma região devem
  receber um mesmo número. Por exemplo, o reticulado acima tem  8
  regiões alagadas maximais. Neste caso, um exemplo de saída seria:

\begin{center}

\begin{tabular}{|r|r|r|r|r|r|r|r|r|r|} \hline
1&0&0&0&0&2&2&0&3&3\\ \hline
1&1&1&0&0&0&2&0&3&0\\ \hline
0&1&0&0&4&0&0&0&0&0\\ \hline
0&0&0&4&4&4&4&4&0&0\\ \hline
0&0&0&0&4&4&0&0&5&5\\ \hline
0&0&6&0&0&0&0&5&5&5\\ \hline 
0&0&6&6&6&0&0&0&5&5\\ \hline
7&0&6&6&6&6&0&0&0&5\\ \hline
7&0&0&0&0&0&8&8&0&0\\ \hline
7&0&0&0&0&0&8&0&0&0\\ \hline
\end{tabular}

\end{center}
 
\item Imprimir a matriz dada $U$ e a matriz marcada $M$.

\newpage     

\item Use obrigatoriamente seguintes funções:
 \begin{itemize}

  \item função {\bf void CriaLista}
   \begin{itemize}
   \item parâmetros:\\
     $m$, $n$: números inteiros \\
     MATRIX: matriz inteira $m\times n$\\
     LISTA: matriz inteira $ (m*n)\times 3$
   \item descrição:\\
     A partir da matriz MATRIX essa função deve construir a matriz
     LISTA. Esta deverá indicar quais são as posições alagadas de
     MATRIX. A informação de que uma posição $(x,y)$ de MATRIX está
     alagada deve ficar armazenada numa linha da matriz LISTA: a
     primeira coluna armazena $x$ e a segunda coluna armazena $y$ (a
     terceira coluna não é alterada por essa função).  Se a matriz
     MATRIX tiver $t$ posições alagadas, então as $t$ primeiras linhas
     (juntamente com as correspondentes duas primeiras colunas) da
     matriz LISTA armazenarão essas informações. As linhas restantes
     deverão conter $-3$ por convenção.
   \end{itemize}

  \item função {\bf int EhVizinho}
   \begin{itemize}
   \item parâmetros de entrada:\\
           $x, y, z, w$: números inteiros
         \item descrição:\\
           se a posição $(x,y)$ for adjacente à posição $(z,w)$, então
           a função deve devolver o valor $1$; caso contrário,
           devolver o valor $0$.
   \end{itemize}

  \item  função {\bf void MarcaComK}
   \begin{itemize}
    \item parâmetros:\\
          $k, lin, m, n $: números inteiros\\
          MAT: matriz inteira $m\times n$\\
          LISTA: matriz inteira $(m*n) \times 3$
        \item descrição:\\
          Esta função recebe como entrada a matriz MAT e a devolve
          marcada. Para isso, ela deve usar as duas funções
          anteriores.  O parâmetro {\em lin} indica qual é a linha da
          matriz LISTA que está sendo usada como ponto de partida para
          atribuição do valor $k$.  Ou seja, a partir da posição
          $(x,y)$ que está na linha {\em lin} da matriz LISTA, deve-se
          percorrer a LISTA e identificar posições que são
          adjacentes a $(x,y)$, e armazenar tanto em ${\rm MAT}(x,y)$
          como na 3a. coluna de LISTA o valor $k$.  Note que as
          posições que estão na LISTA e que receberam o valor $k$ na
          3a. coluna devem agora ser testadas para verificar se têm
          vizinhos adjacentes que também devem receber o valor $k$. Ou
          seja, o processo de marcar o valor $k$ deve continuar
          enquanto houver alguma posição na LISTA que recebeu o valor
          $k$ e ainda não teve os seus vizinhos testados. Nessa função
          você deve usar as duas funções anteriores.
          
          Sugestão: à medida que posições na LISTA vão sendo testadas
          e vão sendo marcadas (com algum inteiro $k$), para indicar
          que estas já foram marcadas, em vez de removê-las da LISTA,
          você pode armazenar nessas posições um valor negativo, como
          por exemplo, $-3$ ou $-4$ para indicar isso.
   \end{itemize}


 

 \end{itemize}

\item {\bf Observações}
\begin{itemize}

\item Para imprimir a matriz, basta imprimir os números (não é
  necessário imprimir as linhas horizontais e verticais).
  
\item Voce deve fazer leitura de dados de um arquivo e impressão da
saída em um arquivo, conforme a nova receita dada (veja na versão html
deste texto). Faça o programa inicialmente com a receita (de
entrada e saída) que foi dada para o EP2 que é mais simples. Quando
estiver tudo certo, use a receita dada aqui para o EP3.

\item Teste o seu programa obrigatoriamente com a matriz dada no
  exemplo ($m=n=10$).
  
\item Você pode utilizar mais outras funções, além das que foram
  mencionadas acima.

\end{itemize}


\item {\bf Bônus (opcional)}
  
  Se, adicionalmente, o seu programa imprimir uma matriz do tipo {\it
    char} correspondente à matriz M (marcada), indicando as regiões
  secas e as diferentes regiões alagadas maximais com caracteres bem
  adequados e bonitos, você receberá uns pontos adicionais na nota
  deste EP3. Use sua imaginação (não precisa necessariamente numerar
  as regiões alagadas)! 

\end{enumerate}


\large{{\bf Boa sorte!}}



\end{document}



