Skip to content

Instantly share code, notes, and snippets.

@kuoe0
Created January 16, 2012 08:25
Show Gist options
  • Save kuoe0/1619732 to your computer and use it in GitHub Desktop.
Save kuoe0/1619732 to your computer and use it in GitHub Desktop.
[UVa] 705 - Slash Maze - http://kuoe0.ch/605/uva-705-slash-maze/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 1010
int R, C;
vector< int > que;
char map[ MAXN ][ MAXN ];
bool visit[ MAXN ][ MAXN ];
int step[ 8 ][ 2 ] = { { -1, -1 }, { -1, 1 }, { 1, 1 }, { 1, -1 },
{ -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
int DFS( int r, int c, int lr, int lc, int s ) {
visit[ r ][ c ] = 1;
que.push_back( r * 1000 + c );
for ( int i = 0; i < 4; ++i ) {
int r2 = r + step[ i ][ 0 ], c2 = c + step[ i ][ 1 ];
if ( r2 >= 0 && r2 < R * 2 && c2 >= 0 && c2 < C * 2 && r2 != lr && c2 != lc ) {
if ( !( i % 2 ) && !map[ r2 ][ c2 ] && map[ r2 ][ c ] == '\\' && map[ r ][ c2 ] == '\\' ) {
if ( !visit[ r2 ][ c2 ] )
return DFS( r2, c2, r, c, s + 1 );
return s + 1;
}
else if ( ( i % 2 ) && !map[ r2 ][ c2 ] && map[ r2 ][ c ] == '/' && map[ r ][ c2 ] == '/' ) {
if ( !visit[ r2 ][ c2 ] )
return DFS( r2, c2, r, c, s + 1 );
return s + 1;
}
}
}
for ( int i = 4; i < 8; ++i ) {
int r2 = r + step[ i ][ 0 ], c2 = c + step[ i ][ 1 ];
if ( r2 >= 0 && r2 < R * 2 && c2 >= 0 && c2 < C * 2 && r2 != lr && c2 != lc && !map[ r2 ][ c2 ] ) {
if ( !visit[ r2 ][ c2 ] )
return DFS( r2, c2, r, c, s + 1 );
return s + 1;
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment