7-1 拯救007 (25分)

在老電影“007之生死關(guān)頭”（Live and Let Die）中有一個(gè)情節(jié)，007被毒販抓到一個(gè)鱷魚池中心的小島上，他用了一種極為大膽的方法逃脫 —— 直接踩著池子里一系列鱷魚的大腦袋跳上岸去！（據(jù)說當(dāng)年替身演員被最后一條鱷魚咬住了腳，幸好穿的是特別加厚的靴子才逃過一劫。）
設(shè)鱷魚池是長寬為100米的方形，中心坐標(biāo)為 (0, 0)，且東北角坐標(biāo)為 (50, 50)。池心島是以 (0, 0) 為圓心、直徑15米的圓。給定池中分布的鱷魚的坐標(biāo)、以及007一次能跳躍的最大距離，你需要告訴他是否有可能逃出生天。
輸入格式：
首先第一行給出兩個(gè)正整數(shù)：鱷魚數(shù)量 N（≤100）和007一次能跳躍的最大距離 D。隨后 N 行，每行給出一條鱷魚的 (x,y) 坐標(biāo)。注意：不會有兩條鱷魚待在同一個(gè)點(diǎn)上。
輸出格式：
如果007有可能逃脫，就在一行中輸出"Yes"，否則輸出"No"。
輸入樣例 1：
14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12

輸出樣例 1：
Yes

輸入樣例 2：
4 13
-12 12
12 12
-12 -12
12 -12

輸出樣例 2：
No

思路：首先審下題，題中背景可以抽象成一個(gè)圖，能否到達(dá)岸上，其實(shí)質(zhì)就是利用深度優(yōu)先遍歷出一條能到達(dá)岸邊的路。能遍歷出來就輸出Yes，否則輸出No

這里我采用鏈表形式來存儲數(shù)據(jù)，利用棧堆來存儲查找

代碼構(gòu)想：
1.Mian類即為圖結(jié)構(gòu)類，再建一個(gè)私有節(jié)點(diǎn)類Node
2.initialize初始化圖
3.Boolean Find（node）查找方法，若找到則返回true，否則返回false

不多說，上代碼！

import java.util.*;public class Main {//節(jié)點(diǎn)個(gè)數(shù)static int num=0;//一次能跳躍的距離static int distance=0;//結(jié)點(diǎn)數(shù)組static Node[] array;public static void main(String[] args) {initialize();for (int j=0;j<num;j++){int dx=array[j].x;int dy=array[j].y;int d=distance+15;//判斷兩點(diǎn)是否連通if (dx*dx+dy*dy<=d*d){//尋找最開始能走的點(diǎn)array[j].isCome=true;if (find(array[j])){System.out.println("Yes");return;}}}System.out.println("No");} //1.Mian類即為圖結(jié)構(gòu)類，再建一個(gè)私有節(jié)點(diǎn)類Nodeprivate static class Node{private int x;private int y;//記錄是否來過boolean isCome=false;public Node(int x, int y) {this.x = x;this.y = y;}}//2.initialize初始化圖public static void initialize(){//創(chuàng)建一個(gè)文本掃描器檢測鍵盤輸入Scanner scanner=new Scanner(System.in);num=scanner.nextInt();distance=scanner.nextInt();array=new Node[num];//初始化每個(gè)結(jié)點(diǎn)for (int i=0;i<num;i++){array[i]=new Node(scanner.nextInt(),scanner.nextInt());}}//3.Boolean Find（node）查找方法，若找到則返回true，否則返回falsestatic Boolean find(Node node){//創(chuàng)建一個(gè)堆棧LinkedList stack=new LinkedList();stack.push(node);Node temp;//這塊地方用了臨時(shí)變量，但我寫代碼的時(shí)候把temp和參數(shù)node變量搞混了，還奇怪了好久，發(fā)現(xiàn)后又沒改全，反反復(fù)復(fù)，我。。。把自己給坑了，害說多都是淚啊！！！！// 可能由于當(dāng)時(shí)寫代碼的時(shí)候已經(jīng)很晚了，腦子不太清醒while (!stack.isEmpty()){temp= (Node) stack.pop();if (50-Math.abs(temp.x)<=distance||50-Math.abs(temp.y)<=distance){return true;}for (int j=0;j<num;j++){if (array[j].isCome==false){int dx=temp.x-array[j].x;int dy=temp.y-array[j].y;//判斷兩點(diǎn)是否連通if (dx*dx+dy*dy<=distance*distance){stack.push(array[j]);//標(biāo)記此節(jié)點(diǎn)已經(jīng)走過，其實(shí)如果返回后說明從此節(jié)點(diǎn)出發(fā)無法到達(dá)array[j].isCome=true;}}}}return false;}}

記錄點(diǎn)滴，樂于分享，轉(zhuǎn)載請注明出處
以夢為馬，不負(fù)人生韶華，我們追夢在路上！
愿與君共勉！
寫于2020.4.18 23:09

總結(jié)

以上是生活随笔為你收集整理的用Java写数据结构作业——7-1 拯救007的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。