1. 拯救007
红色边框为岸边,原点(0,0)代表岛的中心,007(本题主角)在岛上。岛的半径为x1, 007的跳跃半径为x2,求007从岛的中心通过黑点跳跃到岸边的路径。
直到点与岸边重合为结束条件:如图
2. 总体算法
/*
* 此处为图的连通集函数和DFS函数
*/
//**********图的连通集**********
void ListComponents (Graph G)
{
for(each V in G)
{
if (!visited[V])
{
DFS(V);
}
}
}
//**********经典的DFS函数**********
void DFS(Vertex V)
{
visited[V] = true;
for( V的每个邻接点 W )
{
if( !visited[W] )
{
DFS(W);
}
}
}
/*
* 此处为007跳跃路径相关函数(图的路径)
*/
//**********007跳跃的路径**********
void Save007 (Graph G)
{
for(each V in G)
{
if (!visited[V] && FirstJump(V)) // FirstJump代表从岛上第一次调到结点的函数,其半径为岛的半径+跳跃半径
{
answer = DFS(V); // 用answer标记DFS是否到达岸边,如果到达岸边,则将answer标记为“YES”
if ( answer == YES ) // 如果有到达岸边的路径,则跳出此循环
{
break;
}
}
}
if ( answer == YES )
{
output("Yes");
}
else
{
output("No");
}
}
//**********改良的DFS函数**********
int DFS(Vertex V) // 将返回值改为int,为Save007函数中的anwser返回标记(如将YES定义为1,将NO定义为0)
{
visited[V] = true;
if ( IsSafe(V) ) // IsSafe函数表示从当前结点是否能成功调到岸上。如果能,则将answer设置为YES;如果不能,则跳跃下一个邻接点。
{
answer = YES;
}
else
{
for( each W in G )
{
if( !visited[W] && Jump(V, W) ) // Jump函数表示从V是否能跳跃到W
{
answer = DFS(W);
if( anwser == YES ) // 当anwser为YES时, 即代表以及调到岸边,则退出循环
{
break;
}
}
}
}
return answer;
}