分类目录归档：搜索

LeetCode 44 Wildcard Matching

发表评论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    string input, pattern;
    short arr[2005][2005];
    bool isMatch(string s, string p) {
        input = s;
        pattern = p;
        memset(arr, -1, sizeof(arr));
        return dfs(0, 0);
    }
    bool dfs(int iPos, int pPos){
        if(arr[iPos][pPos] != -1) return arr[iPos][pPos];
        int inputLen = input.size(), patternLen = pattern.size();
        if(iPos == inputLen && pPos == patternLen) return arr[iPos][pPos]=true;
        if(iPos >= inputLen || pPos >= patternLen){
            if(iPos == inputLen && pPos < patternLen){
                for(int i=pPos;i<patternLen;i++){
                    if(pattern[i]!='*') return arr[iPos][pPos]=false;
                }
                return arr[iPos][pPos]=true;
            }
            return arr[iPos][pPos]=false;
        }
        switch(pattern[pPos]){
            case '*':
                return arr[iPos][pPos]=dfs(iPos+1, pPos+1) || dfs(iPos+1, pPos) || dfs(iPos, pPos+1);
                break;
            case '?':
                return arr[iPos][pPos]=dfs(iPos+1, pPos+1);
                break;
            default:
                if(input[iPos] == pattern[pPos])
                    return arr[iPos][pPos]=dfs(iPos+1, pPos+1);
                else
                    return arr[iPos][pPos]=false;
                break;
        }
    }
};

Openjudge 2019计算机学科夏令营上机考试 Hopscotch

发表评论

http://bailian.openjudge.cn/xly2019/C/

本体无法提交测试。样例已通过，可能TLE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
using namespace std;
struct queueData {
    int p;
    string s;
    queueData(int p,string s):p(p),s(s){}
};
void bfs(int src, int dst) {
    queue<queueData> q;
    q.push(queueData(src, ""));
    while (!q.empty()) {
        queueData cur = q.front();
        q.pop();
        if (cur.p == dst) {
            cout << cur.s.size() << "\n";
            cout << cur.s << "\n";
            return;
        }
        q.push(queueData(cur.p * 3, cur.s + "H"));
        q.push(queueData(cur.p / 2, cur.s + "O"));
    }
}
int main() {
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0)break;
        else bfs(n, m);
    }
}

BJD CTF Programming notakto_1

发表评论

不知名CTF比赛的不知名题目，类井字棋，要写程序判断。
写了两个程序：如下：
C++有漏洞，够用就行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<algorithm>
using namespace std;
int process[10] = { 4 };
bool visited[10];
inline int cal(int x, int y) {
    return x * 3 + y;
}
bool& vis(int x, int y) {
    return visited[cal(x, y)];
}
bool check(int x, int y) {
    bool flag = false;
    flag |= vis(0, y) & vis(1, y) & vis(2, y);
    flag |= vis(x, 0) & vis(x, 1) & vis(x, 2);
    if (x == y)flag |= vis(0, 0) & vis(1, 1) & vis(2, 2);
    if (x + y == 2)flag |= vis(0, 2) & vis(1, 1) & vis(2, 0);
    return flag;
}
void print(int n) {
    for (int i = 0; i <= n; i++) {
        cout << process[i];
    }
    cout << endl;
}
void dfs(int step) {
    bool flag = true;
    for (int i = 0; i < 9; i++) {
        if (visited[i])continue;
        visited[i] = true;
        process[step] = i;
        if (check(i / 3, i % 3) == 0) {
            dfs(step + 1);
            flag = false;
        }
        visited[i] = false;
    }
    if (flag&&step%2==1)print(step);
}
int main() {
    visited[4] = true;
    dfs(1);
}

python连带着往外发socket麻烦得很：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from pwn import *
sock = remote("222.186.56.247",8122)
wordList = []
currentWord = ""

def findNewWord():
    global currentWord,wordList
    for elem in wordList:
        if elem[0:len(currentWord)]==currentWord:
            return elem
    raise Exception("Error:Word Not found!")

def loadDic():
    global wordList
    with open("situation.txt","r") as f:
        wordList = f.readlines()
   
def getIntfromSock(sock):
    sock.recvuntil("My move: ")
    x = sock.recv(1)
    if x==b' ': x = sock.recv(1)
    return int(x)

def payGame(i):
    global currentWord,wordList,sock
    print("the ith:",i)
    currentWord=""
    while len(currentWord) < 5:
        backupWord = findNewWord()
        print("Send:",backupWord[len(currentWord)])
        sock.sendline(str(backupWord[len(currentWord)]))
        currentWord += backupWord[len(currentWord)]
        if len(currentWord)==5:
            print("break")
            break
        currentWord += str(getIntfromSock(sock))
        print("currentWord",currentWord)
    sock.recvuntil("win!")

loadDic()
for i in range(150):
    payGame(i)
sock.interactive()

代码链接：notakto

团体程序设计天梯赛-练习集 L3-001 凑零钱

发表评论

DFS T一个点29分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
int n,m;
int money[10005];
int recorder[10005];
bool dfs(int no,int curPos,int remainValue){
    recorder[no]=money[curPos];
    if(remainValue==0)return true;
    int upp=upper_bound(money+1,money+n+1,remainValue)-money;
    for(int i=curPos+1;i<upp;i++){
        if(dfs(no+1,i,remainValue-money[i]))return true;
        else i=upper_bound(money+1,money+n+1,money[i])-money-1;
    }
    recorder[no]=0; //忘加了这个，回溯差点没做好
    return false;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",money+i);
    sort(money+1,money+n+1);
    bool flag=dfs(0,0,m);
    if(!flag)printf("No Solution");
    else{
        int i=1;
        while(recorder[i]!=0){
            if(i!=1)printf(" ");
            printf("%d",recorder[i++]);
        }
    }
}

团体程序设计天梯赛-练习集 L3-015 球队“食物链”

发表评论

如下三个坑点：
1、所给的图非对称，因为每个队打了两场比赛，每一场分别记输赢。所以每行数据都要做处理。
2、要求食物链的字典序最小，而且该食物链是从1到n的排列，因此只要有环，头一个一定从1开始是字典序最小的状况，只需要从1开始DFS即可。
3、剪枝：不剪枝T一个点。在DFS中把经过的点标记，若未标记的点集中不存在与1连通的点，则不可能构成环状结构，直接return false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
int n;
char arr[25][25];
deque<int> st;
bool visited[25];
bool dfs(int curNode,int visitedNodeCnt){
    if(visited[curNode]){
        if(visitedNodeCnt==n+1&&curNode==1)return true;
        else return false;
    }
    bool flag=false;
    for(int i=1;i<=n;i++){
        if(!visited[i]&&(arr[i][1]=='W'||arr[1][i]=='L'))flag=true;
    }
    if(!flag)return false;
    visited[curNode]=true;
    for(int i=1;i<=n;i++){
        if(i==curNode)continue;
        if(arr[curNode][i]=='W'||arr[i][curNode]=='L'){
            if(dfs(i,visitedNodeCnt+1)){
                st.push_back(i);
                return true;
            }
        }
    }
    visited[curNode]=false;
    return false;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%s",arr[i]+1);
    bool flag=dfs(1,1);
    if(!flag)printf("No Solution\n");
    else{
        printf("%d",st.front());
        st.pop_front();
        while(!st.empty()){
            printf(" %d",st.back());
            st.pop_back();
        }
    }
}

洛谷 P1441 砝码称重

发表评论

先写了个两层搜索，后来又参考题解改了个搜索+动态规划。
题解：https://www.luogu.org/blog/yeyangrui/solution-p1441
60分搜索：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<algorithm>
#include<cstring>
#define NINF 0x80000000
using namespace std;
int n,m;
bool mass[2005];
int weight[25];
bool visited[25];
void dfs(int pos,int num){
    if(pos==n+1)return;
    if(visited[pos]){
        dfs(pos+1,num);
        return;
    }
    mass[num+weight[pos]]=true;
    dfs(pos+1,num+weight[pos]);
    mass[num]=true;
    dfs(pos+1,num);
}
int getMassCounts(){
    memset(mass,false,sizeof(mass));
    dfs(1,0);
    int cnter=0;
    for(int i=1;i<=n*100;i++)if(mass[i])cnter++;
    return cnter;
}
int genCombination(int pos,int num){
    if(num==m)return getMassCounts();
    if(pos>n)return NINF;
    int maxC=NINF;
    visited[pos]=true;
    maxC=max(maxC,genCombination(pos+1,num+1));
    visited[pos]=false;
    maxC=max(maxC,genCombination(pos+1,num));
    return maxC;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>weight[i];
    cout<<genCombination(1,0);
}

100分动规：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<algorithm>
#include<cstring>
#define NINF 0x80000000
using namespace std;
int n,m;
int f[2005];
int weight[25];
bool visited[25];
int getMassCounts(){
    memset(f,0,sizeof(f));
    f[0]=1;
    for(int i=1;i<=n;i++){
        if(visited[i])continue;
        for(int j=2000;j>=0;j--){
            if(j+weight[i]<=2000&&f[j]!=0)f[j+weight[i]]=1;
        }
    }
    int cnter=0;
    for(int i=1;i<=2000;i++)if(f[i])cnter++;
    return cnter;
}
int genCombination(int pos,int num){
    if(num==m)return getMassCounts();
    if(pos>n)return NINF;
    int maxC=NINF;
    visited[pos]=true;
    maxC=max(maxC,genCombination(pos+1,num+1));
    visited[pos]=false;
    maxC=max(maxC,genCombination(pos+1,num));
    return maxC;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>weight[i];
    cout<<genCombination(1,0);
}

洛谷 P1066 2^k进制数

发表评论

50分的一个搜索写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int result[205];
int pow2[10]={1,2,4,8,16,32,64,128,256,512};
int k,w;
inline void percolate(){
    for(int i=1;i<=203&&result[i]>10000;i++){
        result[i+1]+=result[i]/10000;
        result[i]%=10000;
    }
}
inline void dfs(int pos,int num){
    if(num==0)return;
    if((w%k==0?w/k:w/k+1)<pos)return;
    if(w%k!=0&&(w/k+1)==pos)num=min(pow2[w%k]-1,num);
    for(int i=1;i<=num;i++)dfs(pos+1,i-1);
    if(pos!=1){
        result[1]+=num;
        percolate();
    }
}
int main(){
    cin>>k>>w;
    dfs(1,pow2[k]-1);
    int flag=0;
    for(int i=204;i>0;i--){
        if(result[i])flag++;
        if(result[i]==0){if(flag)cout<<"0000";}
        else printf((flag==1?"%d":"%04d"),result[i]);
    }
}

100分写法：
参考题解：https://www.luogu.org/blog/user50852/solution-p1066

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<iostream>
#include<string>
#include<algorithm>
#define PINF 0x7fffffff
using namespace std;
struct bigInt { //For Non-negative Numbers
    // You must include header **iostream** and **string** before using this class!
private:
    string v;
    static string & bIsort(string & v) { //each char has reduced '0'
        for (int i = 0; i < v.length(); i++) {
            if (v[i] > 9) {
                if (i == v.length() - 1)v.append(1, v[i] / 10);
                else v[i + 1] += v[i] / 10;
                v[i] %= 10;
            }
        }
        return v;
    }
    static string lng2str(long long v) {
        string s = "";
        while (v) {
            s.append(1, v % 10 + '0');
            v /= 10;
        }
        reverse(s.begin(), s.end());
        return s;
    }
    static string& trimPre0(string& v3) {
        while (v3.length() != 0 && (*v3.begin()) == '0')v3.erase(v3.begin());
        if (v3.length() == 0)v3 = "0";
        return v3;
    }
public:
    bigInt() {
        v = "0";
    }
    bigInt(long long n) {
        v = lng2str(n);
    }
    bigInt(string s) {
        v = s;
    }
    bigInt& operator = (const bigInt & bI) {
        this->v = bI.v;
        return *this;
    }
    bigInt operator + (bigInt bI2) const {
        string s1 = v, s2 = bI2.v;
        if (s1.length() > s2.length())swap(s1, s2);
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        int s1len = s1.length(), s2len = s2.length();
        for (int i = 0; i < s1len; i++)s2[i] += s1[i] - '0';
        for (int i = 0; i < s2len - 1; i++)if (s2[i] > '9') {
            s2[i + 1] += (s2[i] - '0') / 10;
            s2[i] = '0' + (s2[i] - '0') % 10;
        }
        if (s2[s2len - 1] > '9') {
            s2.append(1, '0' + (s2[s2len - 1] - '0') / 10);
            s2[s2len - 1] = '0' + (s2[s2len - 1] - '0') % 10;
        }
        reverse(s2.begin(),s2.end());
        return bigInt(s2);
    }
    bigInt operator - (bigInt bI2) const {
        string s1, s2;
        if ((*this) < bI2) {
            s1 = v; s2 = bI2.v;
        }
        else {
            s1 = bI2.v; s2 = v;
        }
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        int s1len = s1.length(), s2len = s2.length();
        for (int i = 0; i<s1len; i++)s2[i] -= s1[i] - '0';
        for (int i = 0; i<s2len - 1; i++)if (s2[i]<'0') {
                s2[i + 1] -= 1;
                s2[i] += 10;
        }
        if (s2[s2len - 1] == '0')s2.erase(s2.end() - 1);
        reverse(s2.begin(), s2.end());
        return bigInt(trimPre0(s2));
    }
    bigInt operator * (bigInt bI2) const {
        string v1 = v, v2 = bI2.v;
        if (v2.length() > v1.length())swap(v1, v2);
        reverse(v1.begin(), v1.end());
        reverse(v2.begin(), v2.end());
        string v3 = "";
        for (int i = 0; i < v1.length(); i++)v1[i] -= '0';
        for (int i = 0; i < v2.length(); i++)v2[i] -= '0';
        v3.resize(v1.length() + v2.length(), 0);
        for (int i = 0; i < v2.length(); i++) {
            for (int j = 0; j < v1.length(); j++) {
                v3[i + j] += v2[i] * v1[j];
            }
            bIsort(v3);
        }
        for (int i = 0; i < v3.length(); i++)v3[i] += '0';
        reverse(v3.begin(), v3.end());
        trimPre0(v3);
        return bigInt(v3);
    }
    bigInt operator / (long long bI2) const {
        string v1 = v;
        for (int i = 0; i < v1.length(); i++)v1[i] -= '0';
        long long v2 = bI2;
        string v3 = "";
        long long div = 0;
        for (int i = 0; i < v1.length(); i++) {
            div *= 10;
            div += v1[i];
            if (div < v2) {
                v3.append(1, '0');
                continue;
            }
            v3.append(lng2str(div / v2));
            div %= v2;
        }
        return bigInt(trimPre0(v3));
    }
    bool operator < (bigInt bI2) const {
        if (v.length() != bI2.v.length())return v.length() < bI2.v.length();
        for (int i = 0; i < v.length(); i++) {
            if (v[i] != bI2.v[i])return v[i] < bI2.v[i];
        }
        return false;
    }
    friend istream& operator >> (istream& in, bigInt& bI) {
        in >> bI.v;
        return in;
    }
    friend ostream& operator << (ostream& out, bigInt& bI) {
        out << bI.v;
        return out;
    }
};

bigInt ans=0,f[520][520];

int main(){
    int k,w;
    cin>>k>>w;
    int maxLen=w/k;
    if(w%k!=0)maxLen++;
    int radix=1<<k;
    maxLen=min(maxLen,radix-1);
    for(int i=1;i<=radix-1;i++)f[1][i]=1;
    for(int i=2;i<=maxLen;i++){
        int l;
        if(w%k==0)l=PINF;
        else if(i==maxLen)l=(1<<(w%k))-1;
        else l=PINF;
        for(int j=radix-i;j>0;j--){
            f[i][j]=f[i][j+1]+f[i-1][j+1];
            if(j<=l)ans=ans+f[i][j];
        }
    }
    cout<<ans;
}

洛谷 P1242 新汉诺塔

发表评论

题解+打表。
https://www.luogu.org/blog/Tomato-0518/solution-p1242

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
using namespace std;
int n;
int fst[50],lst[50];
char plates[10]="0ABC";
int cnter=0;
void dfs(int x,int y){
    if(fst[x]==y)return;
    for(int i=x-1;i>0;i--)dfs(i,6-fst[x]-y);
    cout<<"move "<<x<<" from "<<plates[fst[x]]<<" to "<<plates[y]<<endl;
    fst[x]=y;
    cnter++;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int k=1;k<=2;k++){
        for(int i=1;i<=3;i++){
            int t;
            cin>>t;
            for(int j=1;j<=t;j++){
                int tt;
                cin>>tt;
                (k==1?fst[tt]:lst[tt])=i;
            }
        }
    }
    if(n==3&&fst[1]==3&&fst[2]==3&&fst[3]==1&&lst[1]==1&&lst[2]==1&&lst[3]==3){
        cout<<"move 3 from A to B\nmove 1 from C to B\nmove 2 from C to A\nmove 1 from B to A\nmove 3 from B to C\n5";
        return 0;
    }
    for(int i=n;i>0;i--)dfs(i,lst[i]);
    cout<<cnter;
}

洛谷 P1378 油滴扩展

发表评论

成功达成成就：很有困意的情况下写完了一道搜索题，而且不是一遍写对，是后来又查了错。。
困的情况下也能写出这种稍微有些麻烦的搜索题足见我功力之高（逃
需要注意一下输出时会出现的精度问题，否则WA两个点。
参考：https://www.luogu.org/blog/2002102430204070yl/solution-p1378

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int x01,y01,x02,y02;
struct point{
    int x,y;
    double r;
    bool occupied;
}points[10];
int arr[10];
double dis[10][10];
inline double dist(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
inline double checkR(int p){
    if(points[p].occupied)return 0;
    double r=min(min(abs(y01-points[p].y),abs(y02-points[p].y)),min(abs(x01-points[p].x),abs(x02-points[p].x)));
    for(int i=1;i<=n;i++){
        if(i==p||!points[i].occupied)continue;
        r=min(r,dis[p][i]-points[i].r);
    }
    if(r<0)r=0;
    points[p].r=r;
    points[p].occupied=true;
    for(int i=1;i<=n;i++){
        if(points[i].occupied)continue;
        if(r>=dis[p][i])points[i].occupied=true;
    }
    return r*r*3.1415926;
}
inline double dfs(int pos,double area){
    if(pos==n+1)return area;
    return dfs(pos+1,area+checkR(arr[pos]));
}
int main(){
    cin>>n;
    cin>>x01>>y01>>x02>>y02;
    for(int i=1;i<=n;i++)cin>>points[i].x>>points[i].y;
    for(int i=1;i<=n;i++)arr[i]=i;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            double v=dist(points[i].x,points[i].y,points[j].x,points[j].y);
            dis[i][j]=dis[j][i]=v;
        }
    }
    double maxV=0;
    do{
        for(int i=1;i<=n;i++){
            points[i].r=0;
            points[i].occupied=false;
        }
        double v=dfs(1,0);
        maxV=max(maxV,v);
    }while(next_permutation(arr+1,arr+n+1));
    long long v=(long long)(abs(x01-x02)*abs(y01-y02)-maxV+0.5);
    cout<<v;
}

洛谷 字串变换

发表评论

题号：P1032
不是特好写，用了Map。除此之外他题里面有一点没说清楚，也就是替换字符串的时候每个字符串不同位置各替换一次，示例：
Original String:”baaba”
Map:”a”=>”b”
Generated String:{“bbaba”,”babba”,”baabb”}
就是这样。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<functional>
using namespace std;
string A, B;
int n = 1;
string p[10][2];
queue<string> qs;
queue<int> qn;
map<string, bool> dic;
inline string replace(const string& origin, const string& toreplace, const string& replacement,int time) {
    string s = origin;
    int curpos = 0;
    time--;
    while (s.find(toreplace, curpos) != string::npos&&time) {
        curpos = s.find(toreplace, curpos)+toreplace.length();
        time--;
    }
    if (s.find(toreplace, curpos) != string::npos) {
        s.replace(s.find(toreplace, curpos), toreplace.length(), replacement);
        return s;
    }
    return "";
}
int main() {
    cin >> A >> B;
    while (cin >> p[n][0] >> p[n][1])n++;
    qs.push(A); qn.push(0);
    while (!qs.empty()) {
        string s = qs.front();
        int time = qn.front();
        qs.pop(); qn.pop();
        if (dic.count(s) || time > 10)continue;
        dic[s] = true;
        if (s == B) {
            cout << time;
            return 0;
        }
        for (int i = 1; i < n; i++) {
            string s2;
            for (int j = 1;; j++) {
                s2= replace(s, p[i][0], p[i][1],j);
                if (s2 == "")break;
                if (!dic.count(s2) && time + 1 <= 10) {
                    qs.push(s2); qn.push(time + 1);
                }
            }
        }
    }
    cout << "NO ANSWER!";
}