Submission #1780766
Source Code Expand
#pragma region include #include <iostream> #include <iomanip> #include <stdio.h> #include <sstream> #include <algorithm> #include <iterator> #include <cmath> #include <complex> #include <string> #include <cstring> #include <vector> #include <tuple> #include <bitset> #include <queue> #include <complex> #include <set> #include <map> #include <stack> #include <list> #include <fstream> #include <random> //#include <time.h> #include <ctime> #pragma endregion //#include ///////// #define REP(i, x, n) for(int i = x; i < n; ++i) #define rep(i,n) REP(i,0,n) #define ALL(X) X.begin(), X.end() ///////// #pragma region typedef typedef long long LL; typedef long double LD; typedef unsigned long long ULL; typedef std::pair<LL,LL> PLL;// typedef std::pair<int,int> PII;// #pragma endregion //typedef ////定数 const int INF = (int)1e9; const LL MOD = (LL)1e9+7; const LL LINF = (LL)4e18+20; const LD PI = acos(-1.0); const double EPS = 1e-9; ///////// using namespace::std; void solve(){ int R,C; cin >> R >> C; vector<bool> visit(R*C,false); vector<int> dist(R*C,INF); vector< vector<int> > gra(R*C); vector< vector<int> > fld(R,vector<int>(C) ); int start,goal; for(int r=0;r<R;++r){ string str; cin >> str; for(int c=0;c<C;++c){ if( str[c] == 's' ){ start = r*C + c; fld[r][c] = 0; }else if( str[c] == 't' ){ goal = r*C + c; fld[r][c] = 0; }else{ fld[r][c] = str[c]-'0'; } int id = C*r + c; if( c > 0 ){//左 gra[id].push_back( id - 1 ); } if( c+1 < C ){//右 gra[id].push_back( id + 1 ); } if( r > 0 ){//上 if( r&1 ){//0-index 奇数段 gra[id].push_back( id - C ); if( c+1 < C ){ gra[id].push_back( id - C + 1 ); } }else{//0-index 偶数段 if( c > 0 ){ gra[id].push_back( id - C -1 ); } gra[id].push_back( id - C ); } } if( r+1 < R ){//下 if( r&1 ){ gra[id].push_back( id+C ); if( c+1 < C ){ gra[id].push_back( id+C + 1 ); } }else{ if( c > 0 ){ gra[id].push_back( id+C-1 ); } gra[id].push_back( id+C ); } } } } queue<int> que,next; next.push( start ); dist[start] = 0; while( next.size() ){ que = next; { queue<int> zero; next = zero; } while( que.size() ){ int now = que.front();que.pop(); if( visit[now] ) continue; visit[now] = true; int size = gra[now].size(); for(int i=0;i<size;++i){ int to = gra[now][i]; int to_val = dist[now] + fld[to/C][to%C]; if( dist[to] > to_val ){ dist[to] = to_val; next.push( to ); } } } } cout << dist[goal] << endl; } #pragma region main signed main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;//小数を10進数表示 cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別 solve(); } #pragma endregion //main()
Submission Info
Submission Time | |
---|---|
Task | B - Office Ninja |
User | akarin55 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3029 Byte |
Status | WA |
Exec Time | 4 ms |
Memory | 1024 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 001-sample-01.txt, 002-sample-02.txt, 003-minimum-01.txt, 004-random-01.txt, 005-random-02.txt, 006-random-03.txt, 007-random-04.txt, 008-random-05.txt, 009-random-06.txt, 010-random-07.txt, 011-random-08.txt, 012-random-09.txt, 013-random-10.txt, 014-random-11.txt, 015-random-12.txt, 016-random-13.txt, 017-random-14.txt, 018-random-15.txt, 019-random-16.txt, 020-random-17.txt, 021-random-18.txt, 022-random-19.txt, 023-random-20.txt, 024-maximum-01.txt, 025-maximum-02.txt, 026-maximum-03.txt, 027-maximum-04.txt, 999-handmade-01.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
001-sample-01.txt | AC | 1 ms | 256 KB |
002-sample-02.txt | AC | 1 ms | 256 KB |
003-minimum-01.txt | AC | 1 ms | 256 KB |
004-random-01.txt | WA | 2 ms | 512 KB |
005-random-02.txt | AC | 2 ms | 384 KB |
006-random-03.txt | WA | 2 ms | 384 KB |
007-random-04.txt | WA | 1 ms | 256 KB |
008-random-05.txt | WA | 3 ms | 768 KB |
009-random-06.txt | AC | 1 ms | 256 KB |
010-random-07.txt | WA | 1 ms | 384 KB |
011-random-08.txt | WA | 1 ms | 256 KB |
012-random-09.txt | WA | 2 ms | 384 KB |
013-random-10.txt | AC | 1 ms | 256 KB |
014-random-11.txt | WA | 2 ms | 512 KB |
015-random-12.txt | WA | 1 ms | 256 KB |
016-random-13.txt | WA | 1 ms | 256 KB |
017-random-14.txt | WA | 4 ms | 640 KB |
018-random-15.txt | AC | 1 ms | 256 KB |
019-random-16.txt | AC | 3 ms | 768 KB |
020-random-17.txt | WA | 1 ms | 256 KB |
021-random-18.txt | WA | 2 ms | 512 KB |
022-random-19.txt | WA | 3 ms | 768 KB |
023-random-20.txt | WA | 1 ms | 256 KB |
024-maximum-01.txt | WA | 4 ms | 1024 KB |
025-maximum-02.txt | WA | 4 ms | 1024 KB |
026-maximum-03.txt | WA | 4 ms | 1024 KB |
027-maximum-04.txt | WA | 4 ms | 1024 KB |
999-handmade-01.txt | WA | 4 ms | 1024 KB |