結果

問題 No.5015 Escape from Labyrinth
ユーザー 👑 p-adicp-adic
提出日時 2023-04-29 16:34:22
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,908 bytes
コンパイル時間 3,929 ms
コンパイル使用メモリ 226,476 KB
実行使用メモリ 4,500 KB
スコア 0
最終ジャッジ日時 2023-04-29 16:34:58
合計ジャッジ時間 9,625 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 100
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内:
main.cpp:116:9: 警告: ‘key[0]’ may be used uninitialized [-Wmaybe-uninitialized]
  116 |   search( S , key[0] , key[1] , goal[0] , goal[1] );
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:97:7: 備考: ‘key[0]’ はここで定義されています
   97 |   int key[2];
      |       ^~~
main.cpp:116:9: 警告: ‘goal[1]’ may be used uninitialized [-Wmaybe-uninitialized]
  116 |   search( S , key[0] , key[1] , goal[0] , goal[1] );
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:96:7: 備考: ‘goal[1]’ はここで定義されています
   96 |   int goal[2];
      |       ^~~~
main.cpp:116:9: 警告: ‘goal[0]’ may be used uninitialized [-Wmaybe-uninitialized]
  116 |   search( S , key[0] , key[1] , goal[0] , goal[1] );
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:96:7: 備考: ‘goal[0]’ はここで定義されています
   96 |   int goal[2];
      |       ^~~~
main.cpp:116:9: 警告: ‘key[1]’ may be used uninitialized [-Wmaybe-uninitialized]
  116 |   search( S , key[0] , key[1] , goal[0] , goal[1] );
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:97:7: 備考: ‘key[1]’ はここで定義されています
   97 |   int key[2];
      |       ^~~
main.cpp:115:9: 警告: ‘start[1]’ may be used uninitialized [-Wmaybe-uninitialized]
  115 |   search( S , start[0] , start[1] , key[0] , key[1] );
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:95:7: 備考: ‘start[1]’ はここで定義されています
   95 |   int start[2];
      |       ^~~~~
main.cpp:115:9: 警告: ‘start[0]’ may be used uninitialized [-Wmaybe-uninitialized]
  115 |   search( S , start[0] , start[1] , key[0] , key[1] );
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:95:7: 備考: ‘start[0]’ はここで定義されています
   95 |   int start[2];
      |       ^~~~~

ソースコード

diff # 

#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#include <bits/stdc++.h>
using namespace std;

#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define GETLINE( A ) string A; getline( cin , A )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define QUIT return 0

inline CEXPR( int , N , 60 );
void search( string ( &S )[N] , int i0 , int j0 , int i1 , int j1 )
{
  list<list<pair<int,int> > > path{};
  path.push_back( list<pair<int,int> >() );
  path.front().push_back( pair<int,int>( i0 , j0 ) );
  string d[4] = { "U" , "R" , "D" , "L" };
  int di[4] = { -1 , 0 , 1 , 0 };
  int dj[4] = { 0 , 1 , 0 , -1 };
  string w = "#";
  bool reach[N][N] = {};
  pair<int,int> c{};
  int& i = c.first;
  int& j = c.second;
  list<int> direction{};
  bool found = false;
  while( !found ){
    list<pair<int,int> >& last = path.back();
    list<pair<int,int> > next{};
    FOR_ITR( last , itr , end ){
      FOR( n , 0 , 4 ){
	i = itr->first + di[n];
	j = itr->second + dj[n];
	if( i == i1 && j == j1 ){
	  direction.push_front( n );
	  i1 = itr->first;
	  j1 = itr->second;
	  path.pop_back();
	  found = true;
	  break;
	}
	if( 0 <= i && i < N && 0 <= j && j < N && ! reach[i][j] && S[i].substr( j , 1 ) != w ){
	  reach[i][j] = true;
	  next.push_back( c );
	}
      }
      if( found ){
	break;
      }
    }
    if( !found ){
      assert( ! next.empty() );
      path.push_back( next );
    }
  }
  while( ! path.empty() ){
    list<pair<int,int> >& last = path.back();
    found = false;
    FOR_ITR( last , itr , end ){
      FOR( n , 0 , 4 ){
	i = itr->first + di[n];
	j = itr->second + dj[n];
	if( i == i1 && j == j1 ){
	  direction.push_front( n );
	  i1 = itr->first;
	  j1 = itr->second;
	  path.pop_back();
	  found = true;
	  break;
	}
      }
      if( found ){
	break;
      }
    }
  }
  FOR_ITR( direction , itr , end ){
    cout << "M " <<  d[*itr] << "\n";
  }
  return;
}

int main()
{
  UNTIE;
  GETLINE( NDH );
  string S[N];
  string s = "S";
  string g = "G";
  string k = "K";
  int start[2];
  int goal[2];
  int key[2];
  FOR( i , 0 , N ){
    string& Si = S[i];
    getline( cin , Si );
    FOR( j , 0 , N ){
      string Sij = Si.substr( j , 1 );
      if( Sij == s ){
	start[0] = i;
	start[1] = j;
      } else if( Sij == g ){
	goal[0] = i;
	goal[1] = j;
      } else if( Sij == k ){
	key[0] = i;
	key[1] = j;
      }
    }
  }
  search( S , start[0] , start[1] , key[0] , key[1] );
  search( S , key[0] , key[1] , goal[0] , goal[1] );
  QUIT;
}
0