1533Moving Pegs[暴力+打表]

这个题不是很难，就是暴力模拟一下，利用二进制表示状态，，反正最后一共15种结果，暴力程序跑慢点也没事~，2个程序一个250行的暴力，一个150行的表，也是蛮拼的。。

149330001533Moving PegsAcceptedC++0.0092015-02-06 03:15:36

暴力程序：

#include<cstdio>#include<queue>#include<set>#include<cstring>#include<algorithm>using namespace std;typedef pair<int,int> pill;const int maxd = 20;int n;int st;vector<int>G[maxd][8];vector<int>vis[1<<16];struct Node{int st;vector<int>way;Node(int st){this -> st = st;}};//4164;2>;?61::7;441//4 1 6 4 11 2 15 6 1 10 10 7 14 11 11 4 4 1//4164;2>;?61::7;441//4 1 6 4 11 2 14 11 15 6 1 10 10 7 11 4 4 1queue<Node>q;bool judge(int v){int cnt = 0;for(int i = 0; i < 15; i++)if(v & (1 << i))cnt ++;if(cnt == 14)return true;elsereturn false;}void debug(int n){if(n == 0) return ;debug(n / 2);printf("%d",n % 2);}void init(){//6个方向// 1 2// 34// 5 6//编号1G[1][5].push_back(2);G[1][5].push_back(4);G[1][5].push_back(7);G[1][5].push_back(11);G[1][6].push_back(3);G[1][6].push_back(6);G[1][6].push_back(10);G[1][6].push_back(15);//编号2G[2][2].push_back(1);G[2][4].push_back(3);G[2][5].push_back(4);G[2][5].push_back(7);G[2][5].push_back(11);G[2][6].push_back(5);G[2][6].push_back(9);G[2][6].push_back(14);//编号3G[3][1].push_back(1);G[3][3].push_back(2);G[3][5].push_back(5);G[3][5].push_back(8);G[3][5].push_back(12);G[3][6].push_back(6);G[3][6].push_back(10);G[3][6].push_back(15);//编号4G[4][2].push_back(2);G[4][2].push_back(1);G[4][4].push_back(5);G[4][4].push_back(6);G[4][5].push_back(7);G[4][5].push_back(11);G[4][6].push_back(8);G[4][6].push_back(13);//编号5G[5][1].push_back(2);G[5][2].push_back(3);G[5][3].push_back(4);G[5][4].push_back(6);G[5][5].push_back(8);G[5][5].push_back(12);G[5][6].push_back(9);G[5][6].push_back(14);//编号6G[6][1].push_back(3);G[6][1].push_back(1);G[6][3].push_back(5);G[6][3].push_back(4);G[6][5].push_back(9);G[6][5].push_back(13);G[6][6].push_back(10);G[6][6].push_back(15);//编号7G[7][2].push_back(4);G[7][2].push_back(2);G[7][2].push_back(1);G[7][4].push_back(8);G[7][4].push_back(9);G[7][4].push_back(10);G[7][5].push_back(11);G[7][6].push_back(12);//编号8G[8][1].push_back(4);G[8][2].push_back(5);G[8][2].push_back(3);G[8][3].push_back(7);G[8][4].push_back(9);G[8][4].push_back(10);G[8][5].push_back(12);G[8][6].push_back(13);//编号9G[9][1].push_back(5);G[9][1].push_back(2);G[9][2].push_back(6);G[9][3].push_back(8);G[9][3].push_back(7);G[9][4].push_back(10);G[9][5].push_back(13);G[9][6].push_back(14);//编号10G[10][1].push_back(6);G[10][1].push_back(3);G[10][1].push_back(1);G[10][3].push_back(9);G[10][3].push_back(8);G[10][3].push_back(7);G[10][5].push_back(14);G[10][6].push_back(15);//编号11G[11][2].push_back(7);G[11][2].push_back(4);G[11][2].push_back(2);G[11][2].push_back(1);G[11][4].push_back(12);G[11][4].push_back(13);G[11][4].push_back(14);G[11][4].push_back(15);//编号12G[12][1].push_back(7);G[12][2].push_back(8);G[12][2].push_back(5);G[12][2].push_back(3);G[12][3].push_back(11);G[12][4].push_back(13);G[12][4].push_back(14);G[12][4].push_back(15);//编号13G[13][1].push_back(8);G[13][1].push_back(4);G[13][2].push_back(9);G[13][2].push_back(6);G[13][3].push_back(12);G[13][3].push_back(11);G[13][4].push_back(14);G[13][4].push_back(15);//编号14G[14][1].push_back(9);G[14][1].push_back(5);G[14][1].push_back(2);G[14][2].push_back(10);G[14][3].push_back(13);G[14][3].push_back(12);G[14][3].push_back(11);G[14][4].push_back(15);//编号15G[15][1].push_back(10);G[15][1].push_back(6);G[15][1].push_back(3);G[15][1].push_back(1);G[15][3].push_back(14);G[15][3].push_back(13);G[15][3].push_back(12);G[15][3].push_back(11);}void BFS(){while(!q.empty()) q.pop();Node start(st);q.push(start);vector<int>ans;int isok = 0;while(!q.empty()){Node state = q.front(); q.pop();int now = state.st;if(judge(now)){int e = state.way.size();if(state.way[e – 1] != n) continue;//for(int i = 0; i < state.way.size(); i++)//printf("%d ",state.way[i]);//printf("\n");isok = 1;if(!ans.size()){ans = state.way;}else{int can_add = 0;int L1 = state.way.size();int L2 = ans.size();if(L1 < L2){ans = state.way;}else if(L1 == L2)for(int x = 0; x < L1 && x < L2; x++){if(state.way[x] > ans[x]){can_add = -1;break;}else if(state.way[x] < ans[x]){can_add = 1;break;}}if(can_add == 1){ans = state.way;}else if(can_add == 0 && L1 < L2){ans = state.way;}}}for(int i = 1; i <= 15; i++){if(now & (1 << (i – 1))){//如果这一位为空,从6个方向找可以跳到这里的位置for(int j = 1; j <= 6; j++){int cnt = 0;for(int k = 0; k < G[i][j].size(); k++){int e = G[i][j][k];if(now & (1 << (e – 1)))//如果是空白，跳出循环break;else{cnt ++;if(cnt == 1)//如果不是空白continue;int temp = now;int l;//————————————————-for(l = 0;l <= k; l++){//这一条线上的全部清空//这条线上全部清int c = G[i][j][l];temp |= (1 << (c – 1));}temp = ~temp;temp = temp | (1 << (i – 1));temp = ~temp;//————————————————-Node tmp = state;tmp.st = temp;tmp.way.push_back(e);tmp.way.push_back(i);if(!vis[temp].size()){vis[temp] = tmp.way;q.push(tmp);}else{int can_add = 0;int L1 = tmp.way.size();int L2 = vis[temp].size();for(int x = 0; x < L1 && x < L2; x++){if(tmp.way[x] > vis[temp][x]){can_add = -1;break;}else if(tmp.way[x] < vis[temp][x]){can_add = 1;break;}}if(can_add == 1){vis[temp] = tmp.way;q.push(tmp);}else if(can_add == 0 && L1 < L2){vis[temp] = tmp.way;q.push(tmp);}}}}}}}}if(!isok){printf("IM");}else{printf("%d\n",ans.size() / 2);for(int i = 0; i < ans.size(); i++)printf("%d ",ans[i]);}return;}int main(){int T;init();scanf("%d",&T);while(T–){scanf("%d",&n);st = 0;st |= (1 << (n – 1));BFS();}return 0;}打表：

去旅行不在于记忆，而在于当时的那份心情。