http:⼀⼀acm.hdu.edu.cn⼀showproblem.php?pid=2562 杭电2562题

经典的双向广度搜索，如果是4个方向8步进行搜索的话，其代价是相当高的。所以只能是起点和中点一起搜。当搜到一个相同的位节点的时候，搜索完毕。

#include

#include

#include

using namespace std;

const int MAX=8;

struct node{

int i, j;

};

struct dbfs{

node a[4];

};

int xy[4][2]=, , , };

bool success;

char a[MAX][MAX][MAX][MAX][MAX][MAX][MAX][MAX];

dbfs s;

void init()

{

for(int i=0; i<8; i++)

for(int j=0; j<8; j++)

for(int k=0; k<8; k++)

for(int l=0; l<8; l++)

for(int m=0; m<8; m++)

for(int n=0; n<8; n++)

for(int o=0; o<8; o++)

for(int p=0; p<8; p++)

a[i][j][k][l][m][n][o][p]=50;

}

bool cmp(const node &a1, const node &b1)

{

if(a1.i!=b1.i)

return a1.i
return a1.j
}

void yes()

{

for(int i=0; i<4; i++)

{

s.a[i].i--;

s.a[i].j--;

}

}

void set(dbfs& s, char fuck)

{

a[s.a[0].i][s.a[0].j][s.a[1].i][s.a[1].j][s.a[2].i][s.a[2].j][s.a[3].i][s.a[3].j]=fuck;

}

char get(const dbfs &s)

{

return a[s.a[0].i][s.a[0].j][s.a[1].i][s.a[1].j][s.a[2].i][s.a[2].j][s.a[3].i][s.a[3].j];

}

bool jud(node &t)

{

for(int i=0; i<4; i++)

if(s.a[i].i==t.i&&s.a[i].j==t.j)

return true;

return false;

}

void bfs(queue&Q, bool fuck)

{

while(!Q.empty())

{

s=Q.front();

Q.pop();

if(fuck)

{

if(get(s)==55)

break;

}

else {

if(get(s)==45)

break;

}

for(int l=0; l<4; l++)

for(int k=0; k<4; k++)

{

dbfs t=s;

t.a[l].i+=xy[k][0];

t.a[l].j+=xy[k][1];

if(t.a[l].i<8&&t.a[l].i>=0&&t.a[l].j>=0&&t.a[l].j<8)

{

if(jud(t.a[l]))

{

t.a[l].i+=xy[k][0];

t.a[l].j+=xy[k][1];

if(!(t.a[l].i<8&&t.a[l].i>=0&&t.a[l].j>=0&&t.a[l].j<8)||jud(t.a[l]))

continue;

}

sort(t.a, t.a+4, cmp);

int c=get(t);

if(fuck)

{

if(c<50)

{

success=true;

return;

}

else if(c==50)

{

set(t, get(s)+1);

Q.push(t);

}

}

else {

if(c>50)

{

success=true;

return;

}

else if(c==50)

{

set(t, get(s)-1);

Q.push(t);

}

}

}

}

}

}

int main()

{

//freopen("data.in", "r", stdin);

while(cin>>s.a[0].i>>s.a[0].j)

{

init();

success=false;

queueQ1, Q2;

for(int i=1; i<4; i++)

cin>>s.a[i].i>>s.a[i].j;

yes();

sort(s.a, s.a+4, cmp);

Q1.push(s);

set(s, 51);

for(int i=0; i<4; i++)

cin>>s.a[i].i>>s.a[i].j;

sort(s.a, s.a+4, cmp);

yes();

Q2.push(s);

set(s, 49);

bfs(Q1, true);

bfs(Q2, false);

if(success)

cout<<"YES"<
else cout<<"NO"<
}

}

如果对您有帮助，请记得采纳为满意答案，谢谢！祝您生活愉快！