P9012 [USACO23JAN] Moo Operations B题解

1
int check(string a) {
2
  if (a.size() < 3)  // 不让加字符，小于 3 的肯定就废了
3
    return -1;
4
  int step = 0;
5
  if (a == "MOO")  // 都一样了你还变它干啥，浪费表情(
6
    return step;
7
  string tmp1 = a;
8
  step++;
9
  if (tmp1[0] == 'M')  // 胡乱尝试
10
    tmp1[0] = 'O';
11
  else
12
    tmp1[0] = 'M';
13
  if (tmp1 != "MOO") {
14
    step++;
15
    if (tmp1[2] == 'M')
16
      tmp1[2] = 'O';
17
    else
18
      tmp1[2] = 'M';
19
  } else
20
    return step;
21
  if (tmp1 != "MOO") {
22
    step--;  // 撤销第 1 步操作，所以是--
23
    if (tmp1[0] == 'M')
24
      tmp1[0] = 'O';
25
    else
26
      tmp1[0] = 'M';
27
  } else
28
    return step;
29
  if (tmp1 != "MOO")
30
    return -1;
31
  return step;
32
}

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
int n;
6
string str;
7

8
int min(int a, int b) {
9
  return a > b ? b : a;
10
}
11

12
bool checkSubString(string a, string b) {
13
  int x = a.size(), y = b.size();
14
  if (x <= y) {
15
    for (int i = 0; i < y; i++) {
16
      if (b[i] == a[0]) {
17
        bool flag = true;
18
        for (int j = 0; j < x; j++)
19
          if (b[i + j] == a[j])
20
            continue;
21
          else {
22
            flag = false;
23
            break;
24
          }
25
        if (flag)
26
          return true;
27
      }
28
    }
29
  }
30
  return false;
31
}
32

33
int check(string a) {
34
  if (a.size() < 3)
35
    return -1;
36
  int step = 0;
37
  if (a == "MOO")
38
    return step;
39
  string tmp1 = a;
40
  step++;
41
  if (tmp1[0] == 'M')
42
    tmp1[0] = 'O';
43
  else
44
    tmp1[0] = 'M';
45
  if (tmp1 != "MOO") {
46
    step++;
47
    if (tmp1[2] == 'M')
48
      tmp1[2] = 'O';
49
    else
50
      tmp1[2] = 'M';
51
  } else
52
    return step;
53
  if (tmp1 != "MOO") {
54
    step--;
55
    if (tmp1[0] == 'M')
56
      tmp1[0] = 'O';
57
    else
58
      tmp1[0] = 'M';
59
  } else
60
    return step;
61
  if (tmp1 != "MOO")
62
    return -1;
63
  return step;
64
}
65

66
int checker(string x) {
67
  if (x.size() <= 3)
68
    return check(x);
69
  int mn = 10000;
70
  string a[] = {"OOO", "OOM", "OMO", "OMM", "MOO", "MOM", "MMO", "MMM"};
71
  for (int i = 0; i < 8; i++) {
72
    if (checkSubString(a[i], x)) {
73
      int tmp = check(a[i]);
74
      if (tmp != -1)
75
        mn = min(mn, (tmp + x.size() - 3));
76
    }
77
  }
78
  if (mn == 10000)
79
    return -1;
80
  return mn;
81
}
82

83
int main() {
84
  scanf("%d", &n);
85
  for (int i = 0; i < n; i++) {
86
    cin >> str;
87
    printf("%d\n", checker(str));
88
    str = "";
89
  }
90
  return 0;
91
}