# POI 2 Stage 2 The Right-Turn Drivers' Club ( DP, BFS )

http://main.edu.pl/en/archive/oi/2/kpk

In the first line of the standard input there are two integers separated by a single space: the number of rows and the number of columns . In each of the following lines of the file there is a description of the corresponding row of the map. Such a description has a form of one word of length consisting of digits and . The digit means that the corresponding square is free, and the digit that it is blocked.
Next, in one line, there are two coordinates of the square , separated by a single space: the row number not greater than and the column number not greater than . In the following line there are two coordinates of the square , written the same way.

O( N * M )

```#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
if( x <= v ) return 0;
x = v; return 1;
}

const int MAXN = 100;
const int MAXM = 100;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

int N, M;
string G[ MAXN ];
int sx, sy, gx, gy;

struct qqq{
int a, b, c;
qqq(){}
qqq( int x, int y, int z ){
a = x, b = y, c = z;
}
};

int dp[ MAXN ][ MAXM ][ 4 ];
qqq pre[ MAXN ][ MAXM ][ 4 ];

signed main(){
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < N; ++i ){
cin >> G[ i ];
}
cin >> sx >> sy >> gx >> gy;
--sx, --sy, --gx, --gy;
{
memset( dp, 0x3f3f3f3f, sizeof( dp ) );
queue< qqq > que;
for( int di = 0; di < 4; ++di ){
dp[ sx ][ sy ][ di ] = 0;
que.push( qqq( sx, sy, di ) );
}
while( not que.empty() ){
int x, y, dir; x = que.front().a, y = que.front().b, dir = que.front().c; que.pop();
if( x == gx and y == gy ) break;
for( int di = 0; di < 4; ++di ){
if( ( di + 1 ) % 4 == dir ) continue;
if( ( di + 2 ) % 4 == dir ) continue;
int nx = x + dx[ di ];
int ny = y + dy[ di ];
if( not ( 0 <= nx and nx < N and 0 <= ny and ny < M ) ) continue;
if( G[ nx ][ ny ] == '1' ) continue;
if( upmin( dp[ nx ][ ny ][ di ], dp[ x ][ y ][ dir ] + 1 ) ){
pre[ nx ][ ny ][ di ] = qqq( x, y, dir );
que.push( qqq( nx, ny, di ) );
}
}
}
}
int ans = 0x3f3f3f3f, best;
for( int di = 0; di < 4; ++di ){
if( upmin( ans, dp[ gx ][ gy ][ di ] ) ){
best = di;
}
}
if( ans == 0x3f3f3f3f ){
cout << "NIE\n";
} else{
cout << ans + 1 << "\n";
vector< pair< int, int > > dc;
for( int x = gx, y = gy, d = best; not ( x == sx and y == sy ); ){
int px = pre[ x ][ y ][ d ].a, py = pre[ x ][ y ][ d ].b, pd = pre[ x ][ y ][ d ].c;
dc.push_back( make_pair( px, py ) );
x = px, y = py, d = pd;
}
for( int i = dc.size() - 1; i >= 0; --i ){
cout << dc[ i ].first + 1 << " " << dc[ i ].second + 1 << "\n";
}
cout << gx + 1 << " " << gy + 1 << "\n";
}
return 0;
}
```