2018.10.21 codeforces1071B. Minimum path(dp+욕심+bfs)
#include
using namespace std;
int n,k,mx[2005][2005],maxA;
char mp[2005][2005];
bool vis[2005][2005];
queue<pair<int,int> >q,s;
inline void dfs(int x,int y,int dep){
if(~mx[x][y])return;
if(x==1&&y==1)mx[x][y]=(mp[x][y]=='a');
else{
if(x^1)dfs(x-1,y,dep-1);
if(y^1)dfs(x,y-1,dep-1);
mx[x][y]=(mp[x][y]=='a')+max(mx[x-1][y],mx[x][y-1]);
}
if(dep<maxA)return;
if(mx[x][y]>=dep-k){
if(dep==maxA)q.push(make_pair(x,y));
else if(dep>maxA){
while(!q.empty())q.pop();
q.push(make_pair(x,y)),maxA=dep;
}
}
}
int main(){
memset(mx,-1,sizeof(mx)),scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)scanf("%s",mp[i]+1);
maxA=k;
dfs(n,n,n*2-1);
int sig=26;
string tmp;
for(int i=1;i<=min(maxA,n*2-1);++i)tmp=tmp+'a';
if(maxA>=n*2-1)return cout<<tmp,0;
if(!maxA)q.push(make_pair(1,1)),tmp=tmp+mp[1][1];
for(int i=maxA?maxA+1:2;i<=n*2-1;++i){
sig=26;
while(!q.empty()){
pair<int,int>t=q.front();
q.pop();
int x=t.first,y=t.second,i,j;
i=x+1,j=y;
if(i<=n&&!vis[i][j]){
vis[i][j]=1;
if(mp[i][j]-'a'==sig)s.push(make_pair(i,j));
else if(mp[i][j]-'a'<sig){
while(!s.empty())s.pop();
s.push(make_pair(i,j)),sig=mp[i][j]-'a';
}
}
i=x,j=y+1;
if(j<=n&&!vis[i][j]){
vis[i][j]=1;
if(mp[i][j]-'a'==sig)s.push(make_pair(i,j));
else if(mp[i][j]-'a'<sig){
while(!s.empty())s.pop();
s.push(make_pair(i,j)),sig=mp[i][j]-'a';
}
}
}
tmp=tmp+(char)(sig+'a');
while(!s.empty())q.push(s.front()),s.pop();
}
cout<<tmp;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.