programming-challenges Playing with Wheels (110902) 题解

来源:转载

一开始居然没想到bfs。

#include <iostream>#include <sstream>#include <fstream>#include <string>#include <vector>#include <list>#include <queue>#include <map>#include <set>#include <stack>#include <assert.h>#include <algorithm>#include <math.h>#include <ctime>#include <functional>#include <string.h>#include <stdio.h>#include <numeric>#include <float.h>using namespace std;const int MX = 10000; vector<bool> visited(MX); struct Num { int i1, i2, i3, i4; Num() {} Num(int ai1, int ai2, int ai3, int ai4) : i1(ai1), i2(ai2), i3(ai3), i4(ai4) {} int val() { return i4 * 1000 + i3 * 100 + i2 * 10 + i1; }};bool operator==(const Num& num1, const Num& num2) { return num1.i1 == num2.i1 && num1.i2 == num2.i2 && num1.i3 == num2.i3 && num1.i4 == num2.i4;}vector<Num> badNums;bool check(Num objective, Num num, vector<Num> &nums, vector<bool> &visited, bool &inserted) { if (objective == num) return true; for (int i = 0; i < badNums.size(); i++) { if (num == badNums[i]) { return false; } } if (!visited.at(num.val())) { visited[num.val()] = true; nums.push_back(num); inserted = true; } return false;} int main() { int N; cin >> N; for (int i = 0; i < N; i++) { int i1, i2, i3, i4; cin >> i1 >> i2 >> i3 >> i4; Num current(i1, i2, i3, i4); cin >> i1 >> i2 >> i3 >> i4; Num objective(i1, i2, i3, i4); int badNumber = 0; cin >> badNumber; badNums.clear(); for (int j = 0; j < badNumber; j++) { cin >> i1 >> i2 >> i3 >> i4; badNums.push_back(Num(i1, i2, i3, i4)); } if (current == objective) { cout << 0 << endl; continue; } int times = 0; visited.clear(); visited.resize(MX); vector<Num> bfs[2]; bfs[0].push_back(current); while (true) { times++; bool find = false; bool inserted = false; bfs[times%2].clear(); for (int j = 0; j < bfs[(times + 1) % 2].size(); j++) { Num num = bfs[(times + 1) % 2][j]; Num num1 = num; num1.i1 = (num1.i1 + 1) % 10; find = check(objective, num1, bfs[times%2], visited, inserted); if (find) { break; } Num num2 = num; num2.i1 = (num2.i1 + 9) % 10; find = check(objective, num2, bfs[times % 2], visited, inserted); if (find) { break; } Num num3 = num; num3.i2 = (num3.i2 + 1) % 10; find = check(objective, num3, bfs[times % 2], visited, inserted); if (find) { break; } Num num4 = num; num4.i2 = (num4.i2 + 9) % 10; find = check(objective, num4, bfs[times % 2], visited, inserted); if (find) { break; } Num num5 = num; num5.i3 = (num5.i3 + 1) % 10; find = check(objective, num5, bfs[times % 2], visited, inserted); if (find) { break; } Num num6 = num; num6.i3 = (num6.i3 + 9) % 10; find = check(objective, num6, bfs[times % 2], visited, inserted); if (find) { break; } Num num7 = num; num7.i4 = (num7.i4 + 1) % 10; find = check(objective, num7, bfs[times % 2], visited, inserted); if (find) { break; } Num num8 = num; num8.i4 = (num8.i4 + 9) % 10; find = check(objective, num8, bfs[times % 2], visited, inserted); if (find) { break; } } if (find) { cout << times << endl; break; } else if (!inserted) { cout << -1 << endl; break; } } } return 0; }




分享给朋友:
您可能感兴趣的文章:
随机阅读: