top of page

CCC 2019 Junior J5: Rule of Three Solution



  1. Build two lists wordsrc and worddst to simulate a dictionary.

  2. Because from source word to destination word, only can perform 15 steps, create a visited lists that are set , keep each steps words, the set will keep unique words generated from previous step.

  3. Use DFS to do the generation.

  4. There is auxiliary function "replace(...)", it generate a words list based source word by using the dictionary.


wordsrc = []
worddst = []

visited = [set(), set(), set(), set(), set(),set(), set(), set(), set(), set(),set(), set(), set(),set(), set(),set()]

for i in range(3):
    rss = input().split()
    wordsrc.append(rss[0])
    worddst.append(rss[1])

ss = input().split()
steps = int(ss[0])
src = ss[1]
dst = ss[2]

def replace(word, x, rn):
    list1 = []
    for i in range(len(word)):
        cpos = i
        j = 0
        while j < len(x) and cpos < len(word) and word[cpos] == x[j]:
            cpos += 1
            j += 1
        if j == len(x):
            newword = word[0:i] + worddst[rn] + word[cpos:]
            list1.append([rn+1, i+1, newword])
    return list1

def getdststring(cur,  curstep, records):
    if curstep > steps:
        return False
    if curstep == steps:
        if cur == dst:
            for x in records:
                print(x[0], x[1], x[2])
            return True
        return False
    if cur in visited[curstep]:
        return False
    for i in range(3):
        thelist = replace(cur,wordsrc[i], i)
        for y in thelist:
            tr= records.copy()
            tr.append(y)
            if getdststring(y[2], curstep+1, tr):
                return True
            else:
                visited[curstep+1].add(y[2])
    return False

getdststring(src, 0, [])

Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC '22 J5 - Square Pool

#include<iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool rowcom(pair<int, int> a, pair<int, int> b){ return a.first < b.first; } bool colcom(pair<int,

Comentários


bottom of page