Mapa comentário OBI 2017 P2F2

mapa.cpp

// Mapa - F2P2 - OBI 2017
// Bia Cunha
// Complexidade: O(n)

#include <bits/stdc++.h>

#define MAX 110

using namespace std;

//declara l e c
int l, c;

//as viriáveis que guardarão as coordenadas da origem
int ori_x, ori_y;

//os vetores de direção
int dir_x[4]={1,-1,0,0};
int dir_y[4]={0,0,1,-1};

//matriz que guarda a entrada 
int mat[MAX][MAX];

//matriz que marca quais casas já foram visitadas
int vis[MAX][MAX];

int dfs(int a, int b){
	//check será true se o final do caminho for em (a, b)
	bool check=true;
	
	//marco que visitei (a,  b)
	vis[a][b]=true;
	
	//teste cada uma das direções nas quais o caminho pode continuar
	for(int k=0; k<4; k++){
		int x=a+dir_x[k];
		int y=b+dir_y[k];
		
		//se esse vizinho ainda não foi visitado e ele faz parte do caminho
		if(!vis[x][y] && mat[x][y]=='H'){
			//marca que o caminho não acabou
			check=false;
			
			//chama a DFS para esse vizinho
			dfs(x, y);
		}
	}
	
	//se esse é o fim do caminho, imprime as coordenadas
	//é garantido pelo enunciado que isso só ocorrerá uma vez
	if(check) printf("%d %d", a, b);
}

int main(){
	//lê a quantidade de linhas e colunas
	scanf("%d %d", &l, &c);
	
	//inicializa as bordas da matriz como obstáculos
	//dessa forma, é garantido que a DFS não passará dos limites estabelecidos
	for(int i=0; i<=l+1; i++) mat[i][0]=mat[i][c+1]='.';
	for(int i=0; i<=c+1; i++) mat[0][i]=mat[l+1][i]='.';
	
	//lê os caracteres
	for(int i=1; i<=l; i++)
		for(int j=1; j<=c; j++){
			scanf("%d", &mat[i][j]);
			
			//se essa é a origem, salva as coordenadas
			if(mat[i][j]=='o')
				ori_x=i, ori_y=j;
		}
	
	//começa a dfs a partir da origem
	dfs(ori_x, ori_y);
}