hdu 1515 Anagrams by Stack

6118 단어 stack
문제:
첫째: 두 문자가 같지 않다(즉, 창고 상단 문자와 목표 문자가 같지 않다).이 상황은 처리하기 쉽습니다. 워드와 일치하는 다음 문자를 창고에 넣고, 바늘을 뒤로 옮기면 계속 귀속됩니다.
둘째: 두 문자가 같다(즉 창고 상단 문자와 목표 문자가 같다).이런 상황은 두 가지 선택이 있다
(1) 문자를 창고에 보내고 대상word의 바늘을 뒤로 옮겨 계속 귀속한다.
(2)word와 일치하는 다음 문자를 창고에 넣고 바늘을 뒤로 옮겨 계속 귀속한다.
매번 귀속은 path로 경로를 기록합니다.대상word의 바늘이 마지막 위치를 초과하면 성공합니다. 이 때path를 출력합니다.
#include<stdio.h>

#include<string.h>

#include<stack>

using namespace std;

char str1[1005],str2[1005];

int len1,len2;

char path[2005];

void test(int x,int y,stack<char> st,int t)

{

    int j;



    if(y==len2)

    {

        printf("i ");

        for(j=0; j<t; j++)

            printf("%c ",path[j]);

        printf("
"); return ; } if(st.empty ()) { st.push(str1[x+1]); path[t]='i'; test(x+1,y,st,t+1); st.pop(); return ; } char cur=st.top (); if(x==len1 && cur!=str2[y]) return ; st.push(str1[x+1]); path[t]='i'; test(x+1,y,st,t+1); st.pop(); if(cur==str2[y]) { st.pop(); path[t]='o'; test(x,y+1,st,t+1); st.push(str1[x]); } return ; } int main() { int i,j; while(scanf("%s%s",str1,str2)!=EOF) { len1=strlen(str1); len2=strlen(str2); printf("[
"); if(len1<len2) { printf("]
"); continue; } stack<char> st; st.push(str1[0]); test(0,0,st,0); printf("]
"); } return 0; }

좋은 웹페이지 즐겨찾기