Shuttle Puzzle[USACO]

开始试图找挪动的规律，找了半天，成功的挪动规律虽然没找到，但发现了失败的规律。如果出现两个连续的W或B，而它的连续没能连续到边界，则铁定失败。如：...W..BB..W.. 或者 ..B..WW..B..

于是，可以递归挪动了~，速度很快，基本为0

 

/*
ID: zhangyc1
LANG: C++
TASK: shuttle
*/
#include <fstream>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <stack>
using namespace std;stack<int> s;
int N, nBLeft = 0, nWRight = 0;
ofstream fileout("shuttle.out");
char strShuttle[26];
int nLineCount = 0;void prepairData()
{ifstream filein("shuttle.in");filein >> N;filein.close();memset(strShuttle, 'W', N);strShuttle[N] = ' ';memset(strShuttle + N + 1, 'B', N);
}inline void record(int i)
{s.push(i+1);
}bool move(int nPosSpace, int nStep)
{if (nBLeft == N && nWRight == N){return true;}// 判断上次移动是否造成了 ...W..BB..W.. 或者 ..B..WW..B..出现，如有，则本次移动失败bool bDuplicate = false;int nCheckPos = nPosSpace - nStep;if (nCheckPos > 0 && strShuttle[nCheckPos] == strShuttle[nCheckPos - 1]){// 左侧发生的重复，必为Bif (nBLeft != nCheckPos + 1){bDuplicate = true;}}else if (nCheckPos < 2*N && strShuttle[nCheckPos] == strShuttle[nCheckPos + 1]){// 右侧发生的重复，必为Wif (nWRight != 2 * N + 1 - nCheckPos){bDuplicate = true;}}if (bDuplicate)return false;//依次尝试左2，左1，右1，右2的移动if (nPosSpace >= 2 && strShuttle[nPosSpace - 2] == 'W' && strShuttle[nPosSpace - 1] == 'B'){strShuttle[nPosSpace] = 'W', strShuttle[nPosSpace - 2] = ' ';nBLeft--, nWRight++;if (move(nPosSpace - 2, -2)){record(nPosSpace - 2);return true;}strShuttle[nPosSpace] = ' ', strShuttle[nPosSpace - 2] = 'W';nBLeft++, nWRight--;}if (nPosSpace >= 1 && strShuttle[nPosSpace - 1] == 'W'){strShuttle[nPosSpace] = 'W', strShuttle[nPosSpace - 1] = ' ';nWRight++;if (move(nPosSpace - 1, -1)){record(nPosSpace - 1);return true;}strShuttle[nPosSpace] = ' ', strShuttle[nPosSpace - 1] = 'W';nWRight--;}if (nPosSpace <= 2*N-1 && strShuttle[nPosSpace + 1] == 'B'){strShuttle[nPosSpace] = 'B', strShuttle[nPosSpace + 1] = ' ';nBLeft++;if (move(nPosSpace + 1, 1)){record(nPosSpace + 1);return true;}strShuttle[nPosSpace] = ' ', strShuttle[nPosSpace + 1] = 'B';nBLeft--;}if (nPosSpace <= 2*N-2 && strShuttle[nPosSpace + 1] == 'W' && strShuttle[nPosSpace + 2] == 'B'){strShuttle[nPosSpace] = 'B', strShuttle[nPosSpace + 2] = ' ';nBLeft++, nWRight--;if (move(nPosSpace + 2, 2)){record(nPosSpace + 2);return true;}strShuttle[nPosSpace] = ' ', strShuttle[nPosSpace + 2] = 'B';nBLeft--, nWRight++;}return false;
}void process()
{nWRight = 1;strShuttle[N] = 'W';strShuttle[N-1] = ' ';move(N - 1, -1);fileout << N;nLineCount = 1;while (!s.empty()){int nTemp = s.top();s.pop();if (nLineCount % 20 == 0)fileout << endl;elsefileout << " ";fileout << nTemp;nLineCount++;}fileout << endl;
}int main(){prepairData();process();fileout.close();return 0;
}