poj2264 최단 경로 + 기록 경로 + 문자 조합 + 귀속
처음에는 자신의 사고방식에 따라 썼는데, 왜냐하면 경로를 기록할 줄 모르기 때문이다
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char str1[105],str2[105];
int t[110][110];
char a[110];
int main()
{
while(scanf("%s%s",str1,str2)!=EOF)
{
int len1=strlen(str1);
int len2=strlen(str2);
for(int i=0;i<len1;i++)
for(int j=0;j<len2;j++)
t[i][j]=0;
for(int i=0;i<len1;i++)
for(int j=0;j<len2;j++)
if(str1[i]==str2[j])
t[i+1][j+1]=t[i][j]+1;
else
t[i+1][j+1]=max(t[i][j+1],t[i+1][j]);
int pos=t[len1][len2]-1;
int p=len1,k=len2;
int tag1=1,tag2=1;
while(t[p][k]){
if(t[p][k]==t[p][k-1]){
k--;
tag2=0;
}
else if(t[p][k]==t[p-1][k]){
p--;
tag1=0;
}
else{
if(tag1){
a[pos--]=str2[k-1];
p--;
}
else{
a[pos--]=str1[p-1];
k--;
}
tag1=1;
tag2=1;
}
}
int p1=0,p2=0;
for(int i=0;i<len1;i++)
if(a[0]==str1[i]){
p1=i;
break;
}
else
printf("%c",str1[i]);
for(int j=0;j<len2;j++)
if(a[0]==str2[j]){
p2=j;
break;
}
else
printf("%c",str2[j]);
int i,j;
pos=0;
for(i=p1,j=p2;i<len1||j<len2;)
if(str1[i]==a[pos]&&a[pos]==str2[j]&&i<len1&&j<len2){
printf("%c",str1[i]);
i++;
j++;
pos++;
}
else{
if(i<len1&&str1[i]!=a[pos])
printf("%c",str1[i++]);
else if(j<len2&&a[pos]!=str2[j])
printf("%c",str2[j++]);
}
puts("");
}
return 0;
}
나중에 인터넷에서 다른 사람의 코드를 배워서 귀속+거슬러 올라가기+경로를 기록하는 코드를 이해했다
#include<stdio.h>
#include<string.h>
char str1[105],str2[105];
int path[110][110];
void print(int n,int m){
if(!n&&!m)
return ;
if(path[n][m]==m+1){
print(n-1,m-1);
putchar(str1[n]);
}
else if(path[n][m]==m){
print(n-1,m);
putchar(str1[n]);
}
else{
print(n,m-1);
putchar(str2[m]);
}
return ;
}
int main()
{
while(scanf("%s%s",str1+1,str2+1)!=EOF)
{
int len1=strlen(str1+1);
int len2=strlen(str2+1);
int t[110][110]={0};
for(int i=1;i<=len1;i++)
for(int j=1;j<=len2;j++)
if(str1[i]==str2[j])
t[i][j]=t[i-1][j-1]+1,path[i][j]=j+1;
else if(t[i][j-1]>t[i-1][j])
t[i][j]=t[i][j-1],path[i][j]=j-1;
else
t[i][j]=t[i-1][j],path[i][j]=j;
print(len1,len2);
puts("");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.