Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Algorithm
#include <bits/stdc++.h>
using namespace std;
typedef pair<string, int> P;
//すべての色が同じかを判定
bool judge(string str) {
for (int i = 0; i < str.size(); ++i) {
if (str[0] != str[i]) return false;
}
return true;
}
//隣り合う2色のどちらでもない色を返す
char color(char a, char b){
if((a == 'g' && b == 'r') || (a == 'r' && b == 'g'))return 'b';
else if((a == 'b' && b == 'r') || (a == 'r' && b == 'b')) return 'g';
else if((a == 'g' && b == 'b') || (a == 'b' && b == 'g')) return 'r';
}
int solve(string s ){
queue<P> q;
map<string, int> m;
q.push(P(s, 0)); //キューに初期状態を入れる
while (!q.empty()) { //キューが空の状態になるまで
P p = q.front();
q.pop();
if(m[p.first]) continue; //重複を避ける
string now = p.first;
if (judge(now)) return p.second;
m[p.first] = p.second;
for (int i = 0; i < now.size() - 1; ++i) {
if (now[i] != now[i+1]){ //隣り合う2色が異なるとき
char tmp = color(now[i], now[i + 1]);
string D = now;
D[i] = tmp;
D[i + 1] = tmp;
q.push(P(D, p.second + 1));
}
}
}
return -1;
}
int main() {
string worm;
while (cin >> worm) {
if (worm == "0") break;
int count = solve(worm);
if (count == -1) cout << "NA" << endl;
else cout << count << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment