#UVa:10067-Playing with Wheels

灆洢 2019-04-12 01:17:10

利用 BFS 搜尋即可。可將每一種四位數的齒輪數字利用一個整數去計算,另外對於已經走過的狀態或是被禁止的狀態可以利用一個布林陣列去紀錄,讓你在 BFS 的過程中可以快速查表剪枝。

C++(0.080)

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
using namespace std;

const int WHEEL_COUNT = 4;

struct StateStep{
  int state;
  int step;
};

int inputWheels(){
  int state = 0;
  string temp;
  for(int i = 0 ; i < WHEEL_COUNT ; ++i){
    cin >> temp;
    state = state * 10 + (temp[0] - '0');
  }

  return state;
}

int main(){

  int N;
  while(scanf("%d", &N) != EOF){
    for(int caseNumber = 1 ; caseNumber <= N ; ++caseNumber){
      int initialState = inputWheels();
      int targetState = inputWheels();

      int n;
      vector<bool> forbiddenStates(10000, false);

      scanf("%d", &n);
      for(int i = 0 ; i < n ; ++i){
        forbiddenStates[inputWheels()] = true;
      }

      int totalStep = -1;
      queue<StateStep> states;
      states.push(StateStep{initialState, 0});

      while(!states.empty()){
        StateStep currentState = states.front();
        states.pop();

        if(currentState.state == targetState){
          totalStep = currentState.step;
          break;
        }

        int nextStep = 1;
        for(int i = 0 ; i < WHEEL_COUNT ; ++i, nextStep *= 10){
          int currentWheelState = currentState.state % (nextStep * 10) / nextStep;
          int leftWheelState = (currentWheelState - 1 + 10) % 10;
          int rightWheelState = (currentWheelState + 1) % 10;
          int leftRotateState = currentState.state - currentWheelState * nextStep + leftWheelState * nextStep;
          int rightRotateState = currentState.state - currentWheelState * nextStep + rightWheelState * nextStep;

          if(!forbiddenStates[leftRotateState]) states.push(StateStep {leftRotateState, currentState.step + 1});
          if(!forbiddenStates[rightRotateState]) states.push(StateStep {rightRotateState, currentState.step + 1});
          forbiddenStates[leftRotateState] = true;
          forbiddenStates[rightRotateState] = true;
        }
      }

      printf("%d\n", totalStep);
    }
  }
  return 0;
}

在〈“#UVa:10067-Playing with Wheels”〉中有 1 則留言

#生活趣事:[19.04.08~19.04.14]-初次體驗加分 100% 與初次參與遊戲二創繪圖活動 - 翼世界夢想領域 發表迴響 取消回覆

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料