#864664 (C++17) No.5015 Escape from Labyrinth

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	👑 p-adic
提出日時	2023-04-29 16:41:33
言語	C++17 (gcc 12.3.0 + boost 1.83.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
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,368 KB
testcase_01	AC	3 ms 4,368 KB
testcase_02	AC	2 ms 4,368 KB
testcase_03	AC	3 ms 4,372 KB
testcase_04	AC	2 ms 4,372 KB
testcase_05	AC	2 ms 4,368 KB
testcase_06	AC	2 ms 4,368 KB
testcase_07	AC	2 ms 4,368 KB
testcase_08	AC	2 ms 4,368 KB
testcase_09	AC	3 ms 4,368 KB
testcase_10	AC	3 ms 4,372 KB
testcase_11	AC	2 ms 4,372 KB
testcase_12	AC	2 ms 4,372 KB
testcase_13	AC	2 ms 4,368 KB
testcase_14	AC	3 ms 4,372 KB
testcase_15	AC	2 ms 4,368 KB
testcase_16	AC	2 ms 4,372 KB
testcase_17	AC	3 ms 4,372 KB
testcase_18	AC	2 ms 4,368 KB
testcase_19	AC	2 ms 4,372 KB
testcase_20	AC	3 ms 4,368 KB
testcase_21	AC	2 ms 4,368 KB
testcase_22	AC	2 ms 4,372 KB
testcase_23	AC	2 ms 4,368 KB
testcase_24	AC	2 ms 4,372 KB
testcase_25	AC	2 ms 4,372 KB
testcase_26	AC	3 ms 4,368 KB
testcase_27	AC	2 ms 4,368 KB
testcase_28	AC	2 ms 4,372 KB
testcase_29	AC	2 ms 4,368 KB
testcase_30	AC	2 ms 4,372 KB
testcase_31	AC	3 ms 4,368 KB
testcase_32	AC	2 ms 4,372 KB
testcase_33	AC	2 ms 4,368 KB
testcase_34	AC	2 ms 4,368 KB
testcase_35	AC	3 ms 4,368 KB
testcase_36	AC	2 ms 4,372 KB
testcase_37	AC	2 ms 4,368 KB
testcase_38	AC	3 ms 4,368 KB
testcase_39	AC	2 ms 4,368 KB
testcase_40	AC	2 ms 4,368 KB
testcase_41	AC	2 ms 4,368 KB
testcase_42	AC	2 ms 4,372 KB
testcase_43	AC	3 ms 4,372 KB
testcase_44	AC	2 ms 4,368 KB
testcase_45	AC	2 ms 4,368 KB
testcase_46	AC	2 ms 4,368 KB
testcase_47	AC	2 ms 4,368 KB
testcase_48	AC	2 ms 4,368 KB
testcase_49	AC	2 ms 4,372 KB
testcase_50	AC	2 ms 4,372 KB
testcase_51	AC	2 ms 4,372 KB
testcase_52	AC	2 ms 4,372 KB
testcase_53	AC	2 ms 4,372 KB
testcase_54	AC	2 ms 4,368 KB
testcase_55	AC	2 ms 4,368 KB
testcase_56	AC	2 ms 4,372 KB
testcase_57	AC	2 ms 4,368 KB
testcase_58	AC	2 ms 4,372 KB
testcase_59	AC	2 ms 4,368 KB
testcase_60	AC	2 ms 4,368 KB
testcase_61	AC	2 ms 4,368 KB
testcase_62	AC	2 ms 4,372 KB
testcase_63	AC	2 ms 4,368 KB
testcase_64	AC	2 ms 4,368 KB
testcase_65	AC	2 ms 4,372 KB
testcase_66	AC	3 ms 4,368 KB
testcase_67	AC	2 ms 4,368 KB
testcase_68	AC	2 ms 4,372 KB
testcase_69	AC	2 ms 4,372 KB
testcase_70	AC	2 ms 4,368 KB
testcase_71	AC	2 ms 4,368 KB
testcase_72	AC	2 ms 4,368 KB
testcase_73	AC	2 ms 4,372 KB
testcase_74	AC	2 ms 4,372 KB
testcase_75	AC	2 ms 4,368 KB
testcase_76	AC	2 ms 4,372 KB
testcase_77	AC	2 ms 4,368 KB
testcase_78	AC	2 ms 4,368 KB
testcase_79	AC	2 ms 4,376 KB
testcase_80	AC	2 ms 4,368 KB
testcase_81	AC	2 ms 4,372 KB
testcase_82	AC	2 ms 4,368 KB
testcase_83	AC	2 ms 4,368 KB
testcase_84	AC	2 ms 4,372 KB
testcase_85	AC	2 ms 4,368 KB
testcase_86	AC	2 ms 4,368 KB
testcase_87	AC	2 ms 4,372 KB
testcase_88	AC	2 ms 4,368 KB
testcase_89	AC	2 ms 4,368 KB
testcase_90	AC	2 ms 4,368 KB
testcase_91	AC	2 ms 4,368 KB
testcase_92	AC	2 ms 4,368 KB
testcase_93	AC	2 ms 4,368 KB
testcase_94	AC	2 ms 4,372 KB
testcase_95	AC	2 ms 4,368 KB
testcase_96	AC	2 ms 4,372 KB
testcase_97	AC	2 ms 4,368 KB
testcase_98	AC	3 ms 4,368 KB
testcase_99	AC	3 ms 4,368 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

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];
      |       ^~~~~

ソースコード

raw source code

#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 = "#";
  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;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード