Instantly share code, notes, and snippets.

# microbe8888/aoj0179.cpp Created Feb 4, 2017

What would you like to do?
Algorithm
 #include using namespace std; typedef pair 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

q; map 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; }