敲了一上午 意外的超内存了一次 ！！！！！开始数组开的太大
题意是给你一个棋盘， 有5种不同的棋子，一个车 一个马 一个炮（每个只有一个） 走法按正常棋子走法一样 还有对面一个将 和众多小兵（将和小兵都是不能动的）
问你最少需要走几步能杀死将；
思路： 明显的广搜题
结构体里有车马炮分别的坐标和当前的步数， 按正常的广搜做； 每次都有三种走法 （车 马 炮 ） 而对车又有两种走法 对马有8种走法 （注意蹩马的判断） 对炮友2种走法 注意和车的区别 （车可以都将而炮不能） 然后正常做 判断能不能杀死将车马好说 炮就另加判断 见代码
#include#include #include #include using namespace std ; int mark [11 ][11 ][11 ][11 ][11 ][11 ]; char map [15 ][15 ]; int n ,m ; int dir [8 ][2 ]={-2 ,1 , -1 ,2 , 1 ,2 , 2 ,1 , 2 ,-1 , 1 ,-2 , -1 ,-2 , -2 ,-1 }; int dirt [4 ][2 ]={0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0 }; int xx ,yy ; struct node { int cx ,cy ; int mx ,my ; int px ,py ; int step ; }a ,b ; int min (int x ,int y ) { return x <y ?x :y ; } int max (int x ,int y ) { return x >y ?x :y ; } int bfs (int ci ,int cj ,int mi ,int mj ,int pi ,int pj ) { int i ,j ; memset (mark ,0 ,sizeof(mark )); a .cx =ci ; a .cy =cj ; a .mx =mi ; a .my =mj ; a .px =pi ; a .py =pj ; a .step =0 ; mark [a .cx ][a .cy ][a .mx ][a .my ][a .px ][a .py ]=1 ; queue <node >q ; q .push (a ); int flash =0 ; while(!q .empty ()) { b =q .front (); q .pop (); if(map [b .cx ][b .cy ]=='S' ||map [b .mx ][b .my ]=='S' ) { flash =1 ; printf ("%d\n" ,b .step ); break; } else if(b .px ==xx ) { int cont =0 ; for(i =min (b .py ,yy )+1 ;i <max (b .py ,yy );i ++) { if(map [b .px ][i ]=='D' ) cont ++; else if(i ==b .cy &&b .px ==b .cx ) cont ++; else if(i ==b .my &&b .px ==b .mx ) cont ++; } if(cont ==1 ) { flash =1 ; printf ("%d\n" ,b .step +1 ); break; } } else if(b .py ==yy ) { int cont =0 ; for(i =min (b .px ,xx )+1 ;i <max (b .px ,xx );i ++) { if(map [i ][b .py ]=='D' ) cont ++; else if(i ==b .cx &&b .py ==b .cy ) cont ++; else if(i ==b .mx &&b .py ==b .my ) cont ++; } if(cont ==1 ) { flash =1 ; printf ("%d\n" ,b .step +1 ); break; } } for(i =0 ;i <8 ;i ++) { a =b ; a .step =b .step +1 ; a .mx =b .mx +dir [i ][0 ]; a .my =b .my +dir [i ][1 ]; if(a .mx <0 ||a .mx >=n ||a .my <0 ||a .my >=m ) continue; if(map [a .mx ][a .my ]=='D' ) continue; if(a .mx ==a .cx &&a .my ==a .cy ) continue; if(a .mx ==a .px &&a .my ==a .py ) continue; if(i ==0 ||i ==7 ) { if(map [b .mx -1 ][b .my ]=='D' ||map [b .mx -1 ][b .my ]=='S' ) continue; else if(b .mx -1 ==b .cx &&b .my ==b .cy ) continue; else if(b .mx -1 ==b .px &&b .my ==b .py ) continue; } else if(i ==1 ||i ==2 ) { if(map [b .mx ][b .my +1 ]=='D' ||map [b .mx ][b .my +1 ]=='S' ) continue; else if(b .mx ==b .cx &&b .my +1 ==b .cy ) continue; else if(b .mx ==b .px &&b .my +1 ==b .py ) continue; } else if(i ==3 ||i ==4 ) { if(map [b .mx +1 ][b .my ]=='D' ||map [b .mx +1 ][b .my ]=='S' ) continue; else if(b .mx +1 ==b .cx &&b .my ==a .cy ) continue; else if(b .mx +1 ==b .px &&b .my ==a .py ) continue; } else { if(map [b .mx ][b .my -1 ]=='D' ||map [b .mx ][b .my -1 ]=='S' ) continue; else if(b .mx ==b .cx &&b .my -1 ==b .cy ) continue; else if(b .mx ==b .px &&b .my -1 ==b .py ) continue; } //printf("%d $$$ %d\n",b.mx,b.my); if(mark [a .cx ][a .cy ][a .mx ][a .my ][a .px ][a .py ]==0 ) { mark [a .cx ][a .cy ][a .mx ][a .my ][a .px ][a .py ]=1 ; q .push (a ); } } for(i =0 ;i <4 ;i ++) { for(j =1 ;j <=10 ;j ++) { a =b ; a .step =b .step +1 ; a .cx =dirt [i ][0 ]*j +b .cx ; a .cy =dirt [i ][1 ]*j +b .cy ; if(a .cx <0 ||a .cx >=n ||a .cy <0 ||a .cy >=m ) break; if(map [a .cx