首页 > 代码库 > hdu 3004 The Chess【广独优先搜索】
hdu 3004 The Chess【广独优先搜索】
The Chess
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 466 Accepted Submission(s): 130
All chesses will move in the same way as in real chess games(The chinese chess).
To make the game easier, the opposite‘s chesses will stand still.
Process to the end of file.
5 5 ..DSD ...D. C.... P.D.. ...M. 7 7 .DDSDD. ..DDD.. ...D... .....P. .C..... ...M... .......
Scenario #1 2 Scenario #2 OH!That‘s impossible!
分析：这是一个很好的搜索问题，不知为什么用cin就wa，换成%s就ac了，坑了一天，坑急眼了连饭都没吃。
广搜就是遍历车，马，炮所有的位置状态，开一个6维数组标记3个元素的位置，车，马比较好遍历，车4个方向，马8个·方向，炮除了可以和车一样走外
还可以，还可以“隔山打牛”。注意：马可以被拨马腿，炮不能走到帅的位置上。
代码示例：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
typedef struct
{
int xj,xm,xp;
int yj,ym,yp;
int step;
}node;
int map[11][11],dis[11][11][11][11][11][11];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int dit[8][2]={{2,1},{1,2},{-2,1},{1,-2},{2,-1},{-1,2},{-2,-1},{-1,-2}};
int dic[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,0},{0,1},{-1,0},{0,-1}};
int N,M,ax,ay,bx,by,cx,cy,X,Y;
int min(int a,int b)
{
return a<b?a:b;
}
int max(int a,int b)
{
return a>b?a:b;
}
int bfs()
{
int num,h,t;
node fir,nex;
fir.xj=ax,fir.xm=bx,fir.xp=cx;
fir.yj=ay,fir.ym=by,fir.yp=cy;
fir.step=0;
dis[ax][ay][bx][by][cx][cy]=1;
queue<node>Q;
Q.push(fir);
while(!Q.empty())
{
fir=Q.front();
Q.pop();
map[fir.xj][fir.yj]=1;
map[fir.xm][fir.ym]=1;
map[fir.xp][fir.yp]=1;
for(int i=0;i<8;i++)
{
nex=fir;
nex.xm=fir.xm+dit[i][0];
nex.ym=fir.ym+dit[i][1];
nex.step=fir.step+1;
if((fir.xm+dic[i][0]==X)&&(fir.ym+dic[i][1]==Y))continue;
if(map[fir.xm+dic[i][0]][fir.ym+dic[i][1]])continue;
if(nex.xm>=1&&nex.xm<=N&&nex.ym>=1&&nex.ym<=M&&!map[nex.xm][nex.ym]&&!dis[nex.xj][nex.yj][nex.xm][nex.ym][nex.xp][nex.yp])
{
if(nex.xm==X&&nex.ym==Y)
{
return nex.step;
}
dis[nex.xj][nex.yj][nex.xm][nex.ym][nex.xp][nex.yp]=1;
Q.push(nex);
}
}
for(int i=0;i<4;i++)
{
nex=fir;
nex.xj=fir.xj+dir[i][0];
nex.yj=fir.yj+dir[i][1];
nex.step=fir.step+1;
while(1)
{
if(nex.xj>=1&&nex.xj<=N&&nex.yj>=1&&nex.yj<=M&&!map[nex.xj][nex.yj]&&!dis[nex.xj][nex.yj][nex.xm][nex.ym][nex.xp][nex.yp])
{
if(nex.xj==X&&nex.yj==Y)
{
return nex.step;
}
dis[nex.xj][nex.yj][nex.xm][nex.ym][nex.xp][nex.yp]=1;
Q.push(nex);
}
else
{
break;
}
nex.xj+=dir[i][0];
nex.yj+=dir[i][1];
}
}
for(int i=0;i<4;i++)
{
nex=fir;
nex.xp=fir.xp+dir[i][0];
nex.yp=fir.yp+dir[i][1];
nex.step=fir.step+1;
num=0;
while(1)
{
if(!(nex.xp>=1&&nex.xp<=N&&nex.yp>=1&&nex.yp<=M))break;
if(map[nex.xp][nex.yp])num++;
if(num>1)break;
if(nex.xp==X&&nex.yp==Y&&num==0)
break;
if(nex.xp==X&&nex.yp==Y&&num==1)
{
// printf("<%d,%d>\n",nex.xp,nex.yp);
return nex.step;
}
if(!map[nex.xp][nex.yp]&&!dis[nex.xj][nex.yj][nex.xm][nex.ym][nex.xp][nex.yp]&&num==0)
{
dis[nex.xj][nex.yj][nex.xm][nex.ym][nex.xp][nex.yp]=1;
Q.push(nex);
}
nex.xp+=dir[i][0];
nex.yp+=dir[i][1];
}
}
map[fir.xj][fir.yj]=0;
map[fir.xm][fir.ym]=0;
map[fir.xp][fir.yp]=0;
}
return -1;
}
int main()
{
char c[21][21];
int l=0;
while(~scanf("%d%d",&N,&M))
{
memset(dis,0,sizeof(dis));
for(int i=1;i<=N;i++)
scanf("%s",c[i]+1);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
{
//cin>>c;
if(c[i][j]==‘D‘)
{
map[i][j]=1;
}
else
{
map[i][j]=0;
}
if(c[i][j]==‘S‘)
{
X=i,Y=j;
continue;
}
if(c[i][j]==‘C‘)
{
ax=i,ay=j;
continue;
}
if(c[i][j]==‘M‘)
{
bx=i,by=j;
continue;
}
if(c[i][j]==‘P‘)
{
cx=i,cy=j;
}
}
int time=bfs();
l++;
printf("Scenario #%d\n",l);
if(time==-1)
{
printf("OH!That‘s impossible!\n\n");
}
else
printf("%d\n\n",time);
}
return 0;
}
hdu 3004 The Chess【广独优先搜索】