感謝會長君的指導...現在格式應該正常了...
題目大意:給出一種叫做“大王鮑”的桌游，給出游戲規則和雙方起始的位置，問先走一方能否獲勝...如果不能，問在先走一方走后，后手一方有無必勝策略。
如卓峰君所言...是一道神模擬題...把規則全都寫對了就好...
判斷白贏的方法：檢測棋盤邊上有沒有黑色棋子；如果有，往六個方向搜尋，記錄連成一線的黑色棋子數目；如果黑色棋子數目小于3，再看黑色棋子外側相鄰有沒有白色棋子，記錄連成一線的白色棋子數目；如果白色棋子的數目大于黑色棋子的數目，再判斷白色棋子沿著這個方向能不能推下黑色棋子；如果黑色棋子被推下后黑色棋子數目小于9，則白贏。
如果白不贏，那么枚舉白的所有走法（1個棋子能往6個方向走，2個連成直線的棋子能往6個方向走，還能推動1個黑棋，3個連成直線的棋子能往6個方向走，還能推動1個或2個黑棋。），判斷黑能不能贏...
如果都不贏，就輸出Draw...
代碼如下:
1 //by NKU lkjslkjdlk
2 #include<cstdio>
3 #include<cstring>
4 #include<set>
5 #include<algorithm>
6 #include<iostream>
7
8 using namespace std;
9
10 struct point{
11 int h,l;
12 friend bool operator <(point p1,point p2){return p1.h<p2.h||(p1.h==p2.h&&p1.l<p2.l);}
13 };
14 int h[]={1,1,1,1,1,2,3,4,5,6,7,8,9,9,9,9,9,8,7,6,5,4,3,2};
15 int l[]={5,7,9,11,13,14,15,16,17,16,15,14,13,11,9,7,5,4,3,2,1,2,3,4};
16 int hMove[]={0,-1,-1,0,1,1},lMove[]={-2,-1,1,2,1,-1};
17 int cas,bnum,wnum;char map[19][19];set<point> s,whs;bool hasmove;
18 int judge(char ch1,char ch2){
19 int i,j,cnt1,cnt2;
20 for(i=0;i<24;i++){
21 if(map[h[i]][l[i]]==ch1){
22 for(j=0;j<6;j++){
23 cnt1=1;cnt2=0;
24 if(map[h[i]+hMove[j]][l[i]+lMove[j]]==0||map[h[i]+hMove[j]][l[i]+lMove[j]]=='.')
25 continue;
26 while(map[h[i]+cnt1*hMove[j]][l[i]+cnt1*lMove[j]]==ch1)
27 cnt1++;
28 if(cnt1>=3) continue;
29 while(map[h[i]+(cnt1+cnt2)*hMove[j]][l[i]+(cnt1+cnt2)*lMove[j]]==ch2)
30 cnt2++;
31 if(cnt2>cnt1){
32 if(map[h[i]-hMove[j]][l[i]-lMove[j]]==0){
33 if(ch1=='B'&&bnum-cnt1<9) return 2;
34 if(ch1=='W'&&wnum-cnt1<9) return 0;
35 }
36 }
37 }
38 }
39 }
40 return 1;
41 }
42 int wmove1(int h,int l){
43 int j,flag;bool idx;
44 for(j=0;j<6;j++){
45 idx=false;
46 if(map[h+hMove[j]][l+lMove[j]]=='.'){
47 swap(map[h][l],map[h+hMove[j]][l+lMove[j]]);
48 idx=true;hasmove=true;
49 }
50 if(idx){
51 flag=judge('W','B');
52 swap(map[h][l],map[h+hMove[j]][l+lMove[j]]);
53 if(flag==1) return flag;
54 }
55 }
56 return 0;
57 }
58 int wmove2(int h1,int l1,int h2,int l2){
59 int j,flag;int idx;
60 for(j=0;j<6;j++){
61 idx=0;
62 if(map[h1+hMove[j]][l1+lMove[j]]=='.'&&map[h2+hMove[j]][l2+lMove[j]]=='.'){
63 swap(map[h1][l1],map[h1+hMove[j]][l1+lMove[j]]);
64 swap(map[h2][l2],map[h2+hMove[j]][l2+lMove[j]]);
65 idx=1;
66 }
67 if(h2-h1==hMove[j]&&l2-l1==lMove[j]){
68 if(map[h2+hMove[j]][l2+lMove[j]]=='.'){
69 swap(map[h1][l1],map[h2+hMove[j]][l2+lMove[j]]);
70 idx=2;
71 }
72 if(map[h2+hMove[j]][l2+lMove[j]]=='B'&&map[h2+2*hMove[j]][l2+2*lMove[j]]=='.'){
73 swap(map[h2+hMove[j]][l2+lMove[j]],map[h2+2*hMove[j]][l2+2*lMove[j]]);
74 swap(map[h1][l1],map[h2+hMove[j]][l2+lMove[j]]);
75 idx=3;
76 }
77 if(map[h2+hMove[j]][l2+lMove[j]]=='B'&&map[h2+2*hMove[j]][l2+2*lMove[j]]==0){
78 map[h2+hMove[j]][l2+lMove[j]]='W';
79 map[h1][l1]='.';
80 idx=4;
81 }
82 }
83 if(idx) hasmove=true;
84 if(idx==1){
85 flag=judge('W','B');
86 swap(map[h1][l1],map[h1+hMove[j]][l1+lMove[j]]);
87 swap(map[h2][l2],map[h2+hMove[j]][l2+lMove[j]]);
88 if(flag==1) return flag;
89 }
90 if(idx==2){
91 flag=judge('W','B');
92 swap(map[h1][l1],map[h2+hMove[j]][l2+lMove[j]]);
93 if(flag==1) return flag;
94 }
95 if(idx==3){
96 flag=judge('W','B');
97 swap(map[h1][l1],map[h2+hMove[j]][l2+lMove[j]]);
98 swap(map[h2+hMove[j]][l2+lMove[j]],map[h2+2*hMove[j]][l2+2*lMove[j]]);
99 if(flag==1) return flag;
100 }
101 if(idx==4){
102 flag=judge('W','B');
103 map[h2+hMove[j]][l2+lMove[j]]='B';
104 map[h1][l1]='W';
105 if(flag==1) return flag;
106 }
107 }
108 return 0;
109 }
110 int wmove3(int h1,int l1,int h2,int l2,int h3,int l3)
111 {
112 int j,flag;int idx;
113 for(j=0;j<6;j++){
114 idx=0;
115 if(map[h1+hMove[j]][l1+lMove[j]]=='.'&&map[h2+hMove[j]][l2+lMove[j]]=='.'
116 &&map[h3+hMove[j]][l3+lMove[j]]=='.'){
117 swap(map[h1][l1],map[h1+hMove[j]][l1+lMove[j]]);
118 swap(map[h2][l2],map[h2+hMove[j]][l2+lMove[j]]);
119 swap(map[h3][l3],map[h3+hMove[j]][l3+lMove[j]]);
120 idx=1;
121 }
122 if(h2-h1==hMove[j]&&l2-l1==lMove[j]){
123 if(map[h3+hMove[j]][l3+lMove[j]]=='.'){
124 swap(map[h1][l1],map[h3+hMove[j]][l3+lMove[j]]);
125 idx=2;
126 }
127 if(map[h3+hMove[j]][l3+lMove[j]]=='B'&&map[h3+2*hMove[j]][l3+2*lMove[j]]=='.'){
128 swap(map[h3+hMove[j]][l3+lMove[j]],map[h3+2*hMove[j]][l3+2*lMove[j]]);
129 swap(map[h1][l1],map[h3+hMove[j]][l3+lMove[j]]);
130 idx=3;
131 }
132 if(map[h3+hMove[j]][l3+lMove[j]]=='B'&&map[h3+2*hMove[j]][l3+2*lMove[j]]==0){
133 map[h1][l1]='.';
134 map[h3+hMove[j]][l3+lMove[j]]='W';
135 idx=4;
136 }
137 if(map[h3+hMove[j]][l3+lMove[j]]=='B'&&map[h3+2*hMove[j]][l3+2*lMove[j]]=='B'
138 &&map[h3+3*hMove[j]][l3+3*lMove[j]]=='.'){
139 swap(map[h3+hMove[j]][l3+lMove[j]],map[h3+3*hMove[j]][l3+3*lMove[j]]);
140 swap(map[h1][l1],map[h3+hMove[j]][l3+lMove[j]]);
141 idx=5;
142 }
143 if(map[h3+hMove[j]][l3+lMove[j]]=='B'&&map[h3+2*hMove[j]][l3+2*lMove[j]]=='B'
144 &&map[h3+3*hMove[j]][l3+3*lMove[j]]==0){
145 map[h1][l1]='.';
146 map[h2][l2]='.';
147 map[h3+hMove[j]][l3+lMove[j]]='W';
148 map[h3+2*hMove[j]][l3+2*lMove[j]]='W';
149 idx=6;
150 }
151 }
152 if(idx) hasmove=true;
153 if(idx==1){
154 flag=judge('W','B');
155 swap(map[h1][l1],map[h1+hMove[j]][l1+lMove[j]]);
156 swap(map[h2][l2],map[h2+hMove[j]][l2+lMove[j]]);
157 swap(map[h3][l3],map[h3+hMove[j]][l3+lMove[j]]);
158 if(flag==1) return flag;
159 }
160 if(idx==2){
161 flag=judge('W','B');
162 swap(map[h1][l1],map[h3+hMove[j]][l3+lMove[j]]);
163 if(flag==1) return flag;
164 }
165 if(idx==3){
166 flag=judge('W','B');
167 swap(map[h1][l1],map[h3+hMove[j]][l3+lMove[j]]);
168 swap(map[h3+hMove[j]][l3+lMove[j]],map[h3+2*hMove[j]][l3+2*lMove[j]]);
169 if(flag==1) return flag;
170 }
171 if(idx==4){
172 flag=judge('W','B');
173 map[h3+hMove[j]][l3+lMove[j]]='B';
174 map[h1][l1]='W';
175 if(flag==1) return flag;
176 }
177 if(idx==5){
178 flag=judge('W','B');
179 swap(map[h1][l1],map[h3+hMove[j]][l3+lMove[j]]);
180 swap(map[h3+hMove[j]][l3+lMove[j]],map[h3+3*hMove[j]][l3+3*lMove[j]]);
181 if(flag==1) return flag;
182 }
183 if(idx==6){
184 flag=judge('W','B');
185 map[h1][l1]='W';
186 map[h2][l2]='W';
187 map[h3+hMove[j]][l3+lMove[j]]='B';
188 map[h3+2*hMove[j]][l3+2*lMove[j]]='B';
189 if(flag==1) return flag;
190 }
191 }
192 return 0;
193 }
194 void mycin(){
195 int i;
196 for(i=5;i<=13;i+=2) cin>>map[1][i];
197 for(i=4;i<=14;i+=2) cin>>map[2][i];
198 for(i=3;i<=15;i+=2) cin>>map[3][i];
199 for(i=2;i<=16;i+=2) cin>>map[4][i];
200 for(i=1;i<=17;i+=2) cin>>map[5][i];
201 for(i=2;i<=16;i+=2) cin>>map[6][i];
202 for(i=3;i<=15;i+=2) cin>>map[7][i];
203 for(i=4;i<=14;i+=2) cin>>map[8][i];
204 for(i=5;i<=13;i+=2) cin>>map[9][i];
205 }
206 int main()
207 {
208 int i,j,k=1,flag;point p;
209 set<point>::iterator iter;
210 scanf("%d",&cas);
211 while(cas--){
212 s.clear();whs.clear();hasmove=false;
213 memset(map,0,sizeof(map));
214 mycin();
215 for(i=1,wnum=bnum=0;i<=9;i++){
216 for(j=1;j<=17;j++){
217 if(map[i][j]=='W'){wnum++;p.h=i;p.l=j;whs.insert(p);}
218 if(map[i][j]=='B') bnum++;
219 }
220 }
221 flag=judge('B','W');
222 for(iter=whs.begin();iter!=whs.end()&&flag!=2;iter++){
223 int h1=iter->h,l1=iter->l;
224 flag=wmove1(h1,l1);
225 if(flag==1) break;
226 }
227 for(iter=whs.begin();iter!=whs.end()&&flag!=1&&flag!=2;iter++){
228 for(j=0;j<6&&flag!=1;j++){
229 if(map[iter->h+hMove[j]][iter->l+lMove[j]]=='W'){
230 int h1=iter->h,l1=iter->l,h2=h1+hMove[j],l2=l1+lMove[j];
231 flag=wmove2(h1,l1,h2,l2);
232 if(flag==1) break;
233 }
234 }
235 }
236 for(iter=whs.begin();iter!=whs.end()&&flag!=1&&flag!=2;iter++){
237 for(j=0;j<6&&flag!=1;j++){
238 if(map[iter->h+hMove[j]][iter->l+lMove[j]]=='W'&&map[iter->h+2*hMove[j]][iter->l+2*lMove[j]]=='W'){
239 int h1=iter->h,l1=iter->l,h2=h1+hMove[j],l2=l1+lMove[j],h3=h1+2*hMove[j],l3=l1+2*lMove[j];
240 flag=wmove3(h1,l1,h2,l2,h3,l3);
241 if(flag==1) break;
242 }
243 }
244 }
245 if(hasmove==false&&flag!=2)
246 flag=judge('W','B');
247 printf("Case %d: ",k++);
248 if(flag==0) printf("Black\n");
249 if(flag==1) printf("Draw\n");
250 if(flag==2) printf("White\n");
251 }
252 return 0;
253 }
posted on 2011-10-11 00:39
NKU->lkjslkjdlk 閱讀(746)
評論(0) 編輯 收藏