結果
問題 | No.124 門松列(3) |
ユーザー |
![]() |
提出日時 | 2016-05-25 02:06:26 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 1,647 bytes |
コンパイル時間 | 601 ms |
コンパイル使用メモリ | 73,932 KB |
実行使用メモリ | 7,424 KB |
最終ジャッジ日時 | 2024-10-07 06:56:39 |
合計ジャッジ時間 | 1,704 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <iostream>#include <vector>#include <map>#include <queue>#include <algorithm>using namespace std;#define REP(i,s,e) for (i = s; i <= e; i++)#define rep(i,n) REP (i,0,(int)(n)-1)#define RREP(i,s,e) for (i = s; i >= e; i--)#define rrep(i,n) RREP (i,(int)(n)-1,0)#define INF (int)1e8#define MOD (int)1e9+7typedef long long ll;bool is_kadomatsu(int a, int b, int c) {return a != c && (b < min(a,c) || b > max(a,c));}int dp[100][100][10][10];int main(void) {int i, j, a, b, w, h;int m[100][100];queue<pair<pair<int,int>,pair<int,int>>> q;cin >> w >> h;rep (i,h) rep (j,w) cin >> m[i][j];rep (i,h) rep (j,w) rep (a,10) rep (b,10) dp[i][j][a][b] = INF;q.push(make_pair(make_pair(0,0),make_pair(0,m[0][0])));dp[0][0][0][m[0][0]] = 0;while (!q.empty()) {auto&& p = q.front();i = p.first.first;j = p.first.second;a = p.second.first;b = p.second.second;q.pop();int k;int dxy[4] = {-1,0,1,0};rep (k,4) {int ni = i + dxy[k];int nj = j + dxy[(k+1)%4];if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;if ((is_kadomatsu(a,b,m[ni][nj]) || !a) && dp[ni][nj][b][m[ni][nj]] > dp[i][j][a][b] + 1) {dp[ni][nj][b][m[ni][nj]] = dp[i][j][a][b] + 1;q.push(make_pair(make_pair(ni,nj),make_pair(b,m[ni][nj])));}}}int ans = INF;rep (a,10) rep (b,10) ans = min(ans,dp[h-1][w-1][a][b]);if (ans == INF)cout << -1 << endl;elsecout << ans << endl;return 0;}