网站建设实训报告意见和建议,云南省建设工程造价信息网官网,软件app免费下载大全,聊城集团网站建设价格1004 四子连棋 时间限制: 1 s空间限制: 128000 KB题目等级 : 黄金 Gold题目描述 Description在一个4*4的棋盘上摆放了14颗棋子#xff0c;其中有7颗白色棋子#xff0c;7颗黑色棋子#xff0c;有两个空白地带#xff0c;任何一颗黑白棋子都可以向上下左右四个方向移动到相邻… 1004 四子连棋 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 在一个4*4的棋盘上摆放了14颗棋子其中有7颗白色棋子7颗黑色棋子有两个空白地带任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格这叫行棋一步黑白双方交替走棋任意一方可以先走如果某个时刻使得任意一种颜色的棋子形成四个一线包括斜线这样的状态为目标棋局。 ●○● ○●○●●○●○○●○ 输入描述 Input Description 从文件中读入一个4*4的初始棋局黑棋子用B表示白棋子用W表示空格地带用O表示。 输出描述 Output Description 用最少的步数移动到目标棋局的步数。 样例输入 Sample Input BWBOWBWBBWBWWBWO 样例输出 Sample Output 5 分析 Analysis 搜索经典题 这道题只是看上去很难 首先我们要明确我们要做的事情 输入 判断胜局 行棋 状态储存 状态判重 其中行棋我们有寻找行棋位 判断是否行棋 行棋 对于状态我们有棋盘 序列码Hash码 步数 行棋方 然后打一遍就过了 代码 Code 1 #includecstdio2 #includequeue3 #includeiostream4 #includecstring5 #define LL long long6 using namespace std;7 8 const int dir[4][2] {{0,1},{1,0},{-1,0},{0,-1}};9 int HASH[100000000];10 // State: Map Step Last HashCode?11 // Input:12 // Play: 13 // FindSpace - Move - Hash? - Check? - Push14 // - Print15 // Check:16 // X? - Y? - LU/RU?17 18 struct MAP{19 LL hashcode;20 int map[6][6],last,step;21 22 MAP(){23 memset(map,0,sizeof(map));24 last step hashcode 0;25 }26 };27 28 queueMAP q;29 30 bool check(MAP now){31 for(int i 1;i 4;i)32 if(now.map[i][1] now.map[i][2] now.map[i][2] now.map[i][3] now.map[i][3] now.map[i][4] ||33 now.map[1][i] now.map[2][i] now.map[2][i] now.map[3][i] now.map[3][i] now.map[4][i]){34 return true;35 }36 37 if(now.map[1][1] now.map[2][2] now.map[2][2] now.map[3][3] now.map[3][3] now.map[4][4] ||38 now.map[1][4] now.map[2][3] now.map[2][3] now.map[3][2] now.map[3][2] now.map[4][1]){39 return true; 40 }41 42 return false;43 }44 45 bool GETCODE(MAP now){46 LL code now.hashcode;47 LL cnt 1;48 for(int i 1;i 4;i){49 for(int j 1;j 4;j){50 code now.map[i][j]*cnt;51 cnt * 4;52 }53 }54 code now.last*cnt;55 code % 42137897;56 57 if(HASH[code]) return false;58 else{59 HASH[code] 1;60 return true;61 }62 }63 64 void Input(){65 char ctmp;66 MAP sta;67 for(int i 1;i 4;i){68 for(int j 1;j 4;j){69 cin ctmp;70 switch(ctmp){71 case B: sta.map[i][j] 1; break;72 case W: sta.map[i][j] 2; break;73 }74 }75 }76 77 sta.step 0;78 79 sta.last 1;80 if(GETCODE(sta)) q.push(sta);81 sta.last 2;82 if(GETCODE(sta)) q.push(sta);83 }84 85 void Move(MAP now,int x,int y){86 for(int i 0;i 4;i){87 int nowx xdir[i][0];88 int nowy ydir[i][1];89 90 if(now.map[nowx][nowy] now.last || !now.map[nowx][nowy]) continue;91 92 MAP cnt now;93 94 cnt.map[x][y] cnt.map[nowx][nowy];95 cnt.map[nowx][nowy] 0;96 cnt.last 3-now.last;97 cnt.step now.step1;98 99 if(GETCODE(cnt)) q.push(cnt);
100 }
101 }
102
103 void Findspace(MAP now,int x1,int y1,int x2,int y2){
104 for(int i 1;i 4;i){
105 for(int j 1;j 4;j){
106 if(!now.map[i][j]){
107 if(x1 -1){
108 x1 i,y1 j;
109 }else{
110 x2 i,y2 j;
111 }
112 }
113 }
114 }
115 }
116
117 void bfs(){
118 while(!q.empty()){
119 MAP tmp q.front();
120 q.pop();
121
122 if(check(tmp)){
123 if(!tmp.step) printf(1);
124 else printf(%d,tmp.step);
125 return;
126 }
127
128 int x1 -1,x2 -1,y1 -1,y2 -1;
129
130 Findspace(tmp,x1,y1,x2,y2);
131
132 Move(tmp,x1,y1);
133
134 Move(tmp,x2,y2);
135 }
136 }
137
138 int main(){
139
140 Input();
141 bfs();
142
143 return 0;
144 } 心情很差 转载于:https://www.cnblogs.com/Chorolop/p/7325048.html
