結果
| 問題 | No.367 ナイトの転身 |
| ユーザー |
 mkiken
|
| 提出日時 | 2016-04-30 00:09:56 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 404 ms / 2,000 ms |
| コード長 | 5,654 bytes |
| コンパイル時間 | 801 ms |
| コンパイル使用メモリ | 91,424 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-10-04 23:23:06 |
| 合計ジャッジ時間 | 2,764 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 27 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:134:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
134 | scanf("%d%d", &h, &w);
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:137:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
137 | scanf("%s", tmp);
| ~~~~~^~~~~~~~~~~
ソースコード
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <vector>#include <algorithm>#include <string>#include <map>#include <set>#include <queue>#include <stack>#include <climits>#include <sstream>#include <functional>#include <complex>#include <cassert>using namespace std;#define len(array) (sizeof (array) / sizeof *(array))#define rep(i, s, e) for(int i = (s);i < (e);i++)#define Rep(i, e) for(int i = 0;i < (e);i++)#define rrep(i, e, s) for(int i = (e);(s) <= i;i--)#define Rrep(i, e) for(int i = e;0 <= i;i--)#define mrep(i, e, t1, t2) for(map<t1, t2>::iterator i = e.begin(); i != e.end(); i++)#define vrange(v) v.begin(), v.end()#define vrrange(v) v.rbegin(), v.rend()#define vsort(v) sort(vrange(v))#define vrsort(v) sort(vrrange(v))#define arange(a) a, a + len(a)#define asort(a) sort(arange(a))#define arsort(a, t) sort(arange(a), greater<t>())#define afill(a, v) fill(arange(a), v)#define afill2(a, v, t) fill((t *)(a), (t *)((a) + len(a)), v)#define fmax(a, b) ((a) < (b)? (b) : (a))#define fmin(a, b) ((a) > (b)? (b) : (a))#define fabs(a) ((a) < 0? -(a) : (a))#define pb push_back#define fst(e) (e).first#define snd(e) (e).second#define rg(e, s, t) (s <= e && e < t)#define PQDecl(name, tp) priority_queue< tp, vector<tp>, greater<tp> > name#define dq(q) q.top();q.pop();#define sz(v) ((int)(v).size())#define lg(s) ((int)(s).length())//#define X real()//#define Y imag()//typedef unsigned int ui;typedef long long ll;typedef unsigned long long ull;typedef pair<int, int> P;typedef pair<ll, ll> PL;typedef vector<int> VI;//typedef complex<double> p;const int INF = (int)2e9;const int MOD = (int)1e9 + 7;const double EPS = 1e-10;//const int dx[] = {1, -1, 0, 0, 1, -1, -1, 1};//const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};//const ll weight[] = {1e0,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13};typedef struct _Datum {int fst,snd,trd, fth;_Datum(int arg1 = 0, int arg2 = 0 , int arg3 = 0, int arg4 = 0) {fst = arg1; snd = arg2; trd = arg3, fth = arg4;}bool operator <(const struct _Datum &e) const{return fst == e.fst? (snd == e.snd? trd < e.trd : snd < e.snd) : fst < e.fst;}bool operator >(const struct _Datum &e) const{return fst == e.fst? (snd == e.snd? trd > e.trd : snd > e.snd) : fst > e.fst;}}datum;void prtAI(int *a, int n){Rep(i, n) printf("%d%c", a[i], i==n-1?'\n':' ');}void prtVI(const VI &v){Rep(i, sz(v)) printf("%d%c", v[i], i==sz(v)-1?'\n':' ');}#define MAX_N 100005string field[505];int h, w;int starti, startj;int dp[505][505][2];char tmp[505];PQDecl(pq, datum);void print(int isRed){Rep(i, h){Rep(j, w){printf("%d", dp[i][j][isRed]);}printf("\n");}}// void rec(int i, int j, int turn, int isRed){// if (i < 0 || h <= i || j < 0 || w <= j){// return;// }// if (dp[i][j][isRed] != -1 && dp[i][j][isRed] <= turn){// return;// }// dp[i][j][isRed] = turn;// if (field[i][j] == 'G'){// return;// }// if (field[i][j] == 'R'){// isRed = 1 - isRed;// }// if (isRed){// rec(i+1, j+1, turn+1, isRed);// rec(i+1, j-1, turn+1, isRed);// rec(i-1, j+1, turn+1, isRed);// rec(i-1, j-1, turn+1, isRed);// }// else{// rec(i+1, j+2, turn+1, isRed);// rec(i+1, j-2, turn+1, isRed);// rec(i-1, j+2, turn+1, isRed);// rec(i-1, j-2, turn+1, isRed);// rec(i+2, j+1, turn+1, isRed);// rec(i+2, j-1, turn+1, isRed);// rec(i-2, j+1, turn+1, isRed);// rec(i-2, j-1, turn+1, isRed);// }// }void solve(){afill2(dp, -1, int);scanf("%d%d", &h, &w);Rep(i, h){// cin >> field[i];scanf("%s", tmp);field[i] = tmp;}Rep(i, h)Rep(j, w){if (field[i][j] == 'S'){starti = i;startj = j;break;}}pq.push(datum(0, starti, startj, 0));while(!pq.empty()){datum d = pq.top();pq.pop();int i = d.snd;int j = d.trd;int isRed = d.fth;int turn = d.fst;if (i < 0 || h <= i || j < 0 || w <= j){continue;}if (dp[i][j][isRed] != -1 && dp[i][j][isRed] <= turn){continue;}dp[i][j][isRed] = turn;if (field[i][j] == 'G'){break;}if (field[i][j] == 'R'){isRed = 1 - isRed;}if (isRed){pq.push(datum(turn+1, i+1, j+1, isRed));pq.push(datum(turn+1, i+1, j-1, isRed));pq.push(datum(turn+1, i-1, j+1, isRed));pq.push(datum(turn+1, i-1, j-1, isRed));}else{pq.push(datum(turn+1, i+1, j+2, isRed));pq.push(datum(turn+1, i+1, j-2, isRed));pq.push(datum(turn+1, i-1, j+2, isRed));pq.push(datum(turn+1, i-1, j-2, isRed));pq.push(datum(turn+1, i+2, j+1, isRed));pq.push(datum(turn+1, i+2, j-1, isRed));pq.push(datum(turn+1, i-2, j+1, isRed));pq.push(datum(turn+1, i-2, j-1, isRed));}}// rec(starti, startj, 0, 0);int ans = 0;Rep(i, h)Rep(j, w){if (field[i][j] == 'G'){if (dp[i][j][0] == -1 && dp[i][j][1] == -1){ans = -1;}else{ans = INF;if (dp[i][j][0] != -1){ans = min(ans, dp[i][j][0]);}if (dp[i][j][1] != -1){ans = min(ans, dp[i][j][1]);}}break;}}// print(0);cout << ans << endl;}void doIt(){int t = 1;// scanf("%d", &t);while(t--){solve();}}int main() {doIt();return 0;}