結果
問題 | No.5015 Escape from Labyrinth |
ユーザー |
👑 |
提出日時 | 2023-04-29 16:41:33 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 3,000 ms |
コード長 | 2,975 bytes |
コンパイル時間 | 3,794 ms |
コンパイル使用メモリ | 226,896 KB |
実行使用メモリ | 4,376 KB |
スコア | 11,940 |
最終ジャッジ日時 | 2023-04-29 16:41:46 |
合計ジャッジ時間 | 9,835 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内: main.cpp:120:9: 警告: ‘key[0]’ may be used uninitialized [-Wmaybe-uninitialized] 120 | search( S , key[0] , key[1] , goal[0] , goal[1] ); | ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:101:7: 備考: ‘key[0]’ はここで定義されています 101 | int key[2]; | ^~~ main.cpp:120:9: 警告: ‘goal[1]’ may be used uninitialized [-Wmaybe-uninitialized] 120 | search( S , key[0] , key[1] , goal[0] , goal[1] ); | ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:100:7: 備考: ‘goal[1]’ はここで定義されています 100 | int goal[2]; | ^~~~ main.cpp:120:9: 警告: ‘goal[0]’ may be used uninitialized [-Wmaybe-uninitialized] 120 | search( S , key[0] , key[1] , goal[0] , goal[1] ); | ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:100:7: 備考: ‘goal[0]’ はここで定義されています 100 | int goal[2]; | ^~~~ main.cpp:120:9: 警告: ‘key[1]’ may be used uninitialized [-Wmaybe-uninitialized] 120 | search( S , key[0] , key[1] , goal[0] , goal[1] ); | ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:101:7: 備考: ‘key[1]’ はここで定義されています 101 | int key[2]; | ^~~ main.cpp:119:9: 警告: ‘start[1]’ may be used uninitialized [-Wmaybe-uninitialized] 119 | search( S , start[0] , start[1] , key[0] , key[1] ); | ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:99:7: 備考: ‘start[1]’ はここで定義されています 99 | int start[2]; | ^~~~~ main.cpp:119:9: 警告: ‘start[0]’ may be used uninitialized [-Wmaybe-uninitialized] 119 | search( S , start[0] , start[1] , key[0] , key[1] ); | ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:99:7: 備考: ‘start[0]’ はここで定義されています 99 | int start[2]; | ^~~~~
ソースコード
#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 0inline 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 = "#";string e = "E";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] ){string Sij = S[i].substr( j , 1 );if( Sij != w && Sij != e ){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;}