give you see a 40 points program
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <list>
#include <deque>
#define LL long long
#define db double
#define rint register int
#define R register
#define rep(i,n) for(rint i=1;i<=n;i++)
#define fo(i,x,y) for(rint i=x;i<=y;i++)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define For(a,b,c,d) for(register int a=b;a<=c;a+=d)
#define MAXN 1000001
#pragma GCC optimize(3)
using namespace std;
template <class T> inline void read(register T &x)
{
register long long flag = 1;
x = 0; register char ch = getchar();
for( ; !isdigit(ch) ; ch = getchar() ) if(ch == '-') flag = -1;
for( ; isdigit(ch) ; ch = getchar() ) x = (x << 1) + (x << 3) + (ch ^ 48);
x *= flag;
}
template <class T> inline void write(register T x)
{
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <class T> inline void writeln(register T x)
{
write(x);
puts("");
}
const int dx[ 4 ] = { 0 , 1 , 0 , -1 };
const int dy[ 4 ] = { -1 , 0 , 1 , 0 } ;
int n , m , maze[ 60 ][ 60 ] ;
bool vis[ 20000 ] ;
inline int fun(register int a , register int b , register int c ) { return c * 2700 + a * 51 + b ;}
struct Info
{
int x , y ;
int f ;
int mov ;
} ;
queue <Info> que ;
inline bool zq(register int x , register int y )
{
if( maze[ x ][ y ] || maze[ x + 1 ][ y ] || maze[ x ][ y + 1 ] || maze[ x + 1 ][ y + 1 ] )
return 1 ;
return 0 ;
}
inline void bfs()
{
int x , y , tx , ty , f , d , mov , lx , ly ;
char c ;
read(x); read(y); read(tx); read(ty);
c = getchar();
switch( c )
{
case 'N': f = 0 ;
break ;
case 'E': f = 1 ;
break ;
case 'S': f = 2 ;
break ;
case 'W': f = 3 ;
break ;
}
Info info ;
info.x = x , info.y = y , info.f = f , info.mov = 0 ;
que.push( info ) ;
while( !que.empty() )
{
info = que.front() ;
que.pop() ;
x = info.x , y = info.y , f = info.f , d = fun( x , y , f ) , mov = info.mov ;
if( x == tx && y == ty )
{
writeln(mov) ;
exit( 0 ) ;
}
if( vis[ d ] )
continue ;
vis[ d ] = 1 ;
info.mov ++ ;
info.f = ( f + 4 - 1 ) % 4 ;
que.push( info ) ;
info.f = ( f + 4 + 1 ) % 4 ;
que.push( info ) ;
info.f = f ;
For( i , 1 , 3 , 1 )
{
lx = x + dx[ f ] * i , ly = y + dy[ f ] * i ;
if( lx <= 0 || ly <= 0 || lx >= n || ly >= m || zq( lx , ly ) )
break ;
info.x = lx ;
info.y = ly ;
que.push( info ) ;
}
}
puts("-1");
}
int main(void)
{
read(n); read(m);
For( i , 1 , n , 1 )
{
For( j , 1 , m , 1 )
{
read(maze[ i ][ j ]);
}
}
bfs() ;
return 0;
}
by EternalEpic @ 2018-08-19 21:06:34