結果
問題 | No.124 門松列(3) |
ユーザー |
![]() |
提出日時 | 2015-01-12 00:03:34 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 2,151 bytes |
コンパイル時間 | 759 ms |
コンパイル使用メモリ | 97,000 KB |
実行使用メモリ | 7,452 KB |
最終ジャッジ日時 | 2024-06-22 04:06:09 |
合計ジャッジ時間 | 1,675 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <algorithm>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstdlib>#include <cstring>#include <functional>#include <iostream>#include <map>#include <memory>#include <queue>#include <set>#include <sstream>#include <stack>#include <string>#include <utility>#include <vector>using namespace std;#define sz size()#define pb push_back#define mp make_pair#define fi first#define se second#define all(c) (c).begin(), (c).end()#define rep(i,a,b) for(int i=(a);i<(b);++i)#define clr(a, b) memset((a), (b) ,sizeof(a))#define MOD 1000000009int dp[100][100][10][10];int d[101][101];int isK(int a, int b, int c){if(a==b||b==c||a==c)return 0;int d = b;vector<int> v;v.pb(a);v.pb(b);v.pb(c);sort(all(v));if(d==v[0]||d==v[2])return 1;return 0;}int main(){static int dx[4] = {-1, 0, 0, 1};static int dy[4] = {0, -1, 1, 0};int w,h;cin>>w>>h;rep(y,0,h){rep(x,0,w){char a;cin>>a;d[y][x] = a-'0';}}clr(dp,0);queue<int> qy,qx;queue<int> a1,a2;queue<int> qc;qy.push(0);qx.push(0);a1.push(d[0][0]);a2.push(0);qc.push(0);while(!qy.empty()){int yy = qy.front();qy.pop();int xx = qx.front();qx.pop();int aa1 = a1.front();a1.pop();int aa2 = a2.front();a2.pop();int cc = qc.front();qc.pop();rep(i,0,4){int cy = yy+dy[i];int cx = xx+dx[i];if(0>cy||cy>=h)continue;if(0>cx||cx>=w)continue;if(aa2==0){if(dp[cy][cx][aa1][aa2]!=0)continue;dp[cy][cx][aa1][aa2]=1;qy.push(cy);qx.push(cx);a1.push(d[cy][cx]);a2.push(aa1);qc.push(cc+1);}else{if(dp[cy][cx][aa1][aa2]!=0)continue;dp[cy][cx][aa1][aa2]=1;if(isK(d[cy][cx],aa1,aa2) == 1){if(cy==h-1&&cx==w-1){cout << cc+1 << endl;return 0;}qy.push(cy);qx.push(cx);a1.push(d[cy][cx]);a2.push(aa1);qc.push(cc+1);}}}}cout << -1 << endl;return 0;}