結果
問題 | No.124 門松列(3) |
ユーザー |
|
提出日時 | 2015-01-10 18:26:45 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 1,452 bytes |
コンパイル時間 | 1,359 ms |
コンパイル使用メモリ | 163,048 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-13 03:34:43 |
合計ジャッジ時間 | 2,334 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int INF = 1 << 25;int dy[] = {0, 0, 1, -1};int dx[] = {1, -1, 0, 0};int W, H, M[111][111];int dist[111][111][11];struct State { int y, x, pre; };bool is_kadomatu(int a, int b, int c){if(a < b && c < b && a != c)return true;if(a > b && c > b && a != c)return true;return false;}int main(){cin >> W >> H;for(int i=0;i<H;i++)for(int j=0;j<W;j++)cin >> M[i][j];for(int i=0;i<H;i++)for(int j=0;j<W;j++)for(int k=1;k<=9;k++)dist[i][j][k] = INF;queue<State> Q;// first stepfor(int i=0;i<4;i++){int pre = M[0][0];int ny = dy[i];int nx = dx[i];if(ny < 0 || nx < 0 || ny >= H || nx >= W)continue;if(M[ny][nx] == pre)continue;dist[ny][nx][pre] = 1;Q.push(State{ny, nx, pre});}while(!Q.empty()){auto st = Q.front(); Q.pop();int y = st.y;int x = st.x;int pre = st.pre;int crr = M[y][x];int cost = dist[y][x][pre];for(int i=0;i<4;i++){int ny = y + dy[i];int nx = x + dx[i];int nc = cost + 1;if(ny < 0 || nx < 0 || ny >= H || nx >= W)continue;if(!is_kadomatu(pre, crr, M[ny][nx]))continue;if(nc >= dist[ny][nx][crr])continue;dist[ny][nx][crr] = nc;Q.push(State{ny, nx, crr});}}int res = INF;for(int k=1;k<=9;k++)res = min(res, dist[H-1][W-1][k]);if(res >= INF)res = -1;cout << res << endl;return 0;}