Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
105 lines (86 sloc) 1.92 KB
/**
Jorge Alejandro Jimenez Luna
Algorithm: BFS (Matrix)
*/
#include <bits/stdc++.h>
#define oo 1005
using namespace std;
struct two
{
int f, c;
two(int a = 0, int b = 0)
{
f = a;
c = b;
}
};
const int Mf [] = {1, -1, 0, 0};
const int Mc [] = {0, 0, 1, -1};
int N, M, CA[oo][oo];
bool Mk[oo][oo];
queue<two> Q;
bool isPossible (int f, int c) ///Saber si es posible el movimiento hacia esa casilla
{
if(f < 0 || f > N - 1 || c < 0 || c > M - 1 || Mk[f][c])
return false;
return true;
}
void BFS ()
{
int F, C;
while(!Q.empty())
{
F = Q.front().f;
C = Q.front().c;
Q.pop();
for(int i = 0; i < 4; i++)
{
int nf = F + Mf[i];
int nc = C + Mc[i];
if(isPossible(nf, nc))
{
CA[nf][nc] = CA[F][C] + 1;
Mk[nf][nc] = true;
Q.push(two (nf, nc));
}
}
}
}
int main ()
{
freopen("BFS.in", "r", stdin);
freopen("BFS.out", "w", stdout);
int X = 0;
two _s, _e; ///Punto de Inicio
cin >> N >> M;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
scanf("%s", &X); ///Leer como caracter pero asignar a numero
if(X == 83) ///Inicio Letra - S
{
_s.f = i;
_s.c = j;
continue;
}
if(X == 69) ///Final Letra - E
{
_e.f = i;
_e.c = j;
continue;
}
if(X == 1) ///Rocas
{
Mk[i][j] = true;
continue;
}
}
}
Q.push(two (_s.f, _s.c));
CA[0][0] = 0;
Mk[0][0] = true;
BFS();
printf("%d\n", CA[_e.f][_e.c]);
return 0;
}