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.

解法：
一個頗裸的 DP 和 BFS，DP 記錄方向狀態就能避免左轉或倒走。

時間 / 空間複雜度：
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;
}