Reindeer with no sense of direction (方向音痴のトナカイ)
JOI難易度8の問題ですね。
Reindeer with no sense of direction | Aizu Online Judge
まあ、1<=N,M<=100なので全探索できそうってなったので全探索をした。
当然めちゃくちゃ遅い。
そこで空き地は移動するのに意味がないので家から家(教会)に飛ぶように変えることで遷移が結構減った。
これで一応、JOI予選だったらそこそこ待てば答えがでる。
#include<bits/stdc++.h> #define int long long #define PB push_back #define MP make_pair #define FI first #define SE second using namespace std; static const int INF = 1ll<<60; typedef pair<int,int> pii; const int dx[]={-1,1,0,0}; const int dy[]={0,0,-1,1}; int N,M; int feld[11][11]; int cnt; pii last; int ans; void dfs(int x,int y,int sum){ for(int i=0;i<4;++i){ int nx=x; int ny=y; while(1){ nx+=dx[i]; ny+=dy[i]; if(nx<0||nx>=N||ny<0||ny>=M)break; if(feld[ny][nx]==-1)break; if(feld[ny][nx]==1){ feld[ny][nx]=-1; dfs(nx,ny,sum+1); feld[ny][nx]=1; } else if(feld[ny][nx]==2){ if(sum==cnt){ ans++; return ; } } } } return ; } signed main(){ while(1){ cin>>N>>M; if(N==0&&M==0)break; memset(feld,-1,sizeof(feld)); for(int i=0;i<M;++i){ for(int j=0;j<N;++j){ cin>>feld[i][j]; if(feld[i][j]==2){ last.FI=i; last.SE=j; } else if(feld[i][j]==1)cnt++; } } dfs(last.SE,last.FI,0); cout<<ans<<endl; ans=0; cnt=0; } }
しかしAOJではTLEなのでダメ。
もう少し考えると、すでに配り終わった状態からプレゼントを回収するというのを思いつく。
プレゼントを回収していないところは上空を飛ぶことができず、降り立ってプレゼントを回収し教会へ戻るというふうにすることで遷移の数が減り計算量もいい感じになった。
#include<bits/stdc++.h> #define int long long #define PB push_back #define MP make_pair #define FI first #define SE second using namespace std; static const int INF = 1ll<<60; typedef pair<int,int> pii; const int dx[]={-1,1,0,0}; const int dy[]={0,0,-1,1}; int N,M; int feld[11][11]; int cnt; pii last; int ans; void dfs(int x,int y,int sum){ for(int i=0;i<4;++i){ int nx=x; int ny=y; while(1){ nx+=dx[i]; ny+=dy[i]; if(nx<0||nx>=N||ny<0||ny>=M)break; if(feld[ny][nx]==1){ feld[ny][nx]=-1; dfs(nx,ny,sum+1); feld[ny][nx]=1; break; } else if(feld[ny][nx]==2){ if(sum==cnt){ ans++; return ; } } } } return ; } signed main(){ while(1){ cin>>N>>M; if(N==0&&M==0)break; memset(feld,-1,sizeof(feld)); for(int i=0;i<M;++i){ for(int j=0;j<N;++j){ cin>>feld[i][j]; if(feld[i][j]==2){ last.FI=i; last.SE=j; } else if(feld[i][j]==1)cnt++; } } dfs(last.SE,last.FI,0); cout<<ans<<endl; ans=0; cnt=0; } }
はい(AC)
かなり時間をかけたのでもっと精進が必要ですね。