[UVa] 705 - Slash Maze - http://kuoe0.ch/605/uva-705-slash-maze/

705 - Slash Maze.cpp

#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;
}