リンク

開始リンク

質問する

姜浩はコード教育を行う創業リンクに応募した.今日は江湖の面接の日です.しかし、朝寝坊した姜浩は、スタートリンクのある建物に遅れて到着した.
スタート地点はF階建ての高層ビルにオフィスがあり、スタート地点の位置はG階です.江湖は今S階にいます.今エレベーターでG階に行きます.
一般的にエレベーターにはある階に移動できるボタンがありますが、江湖で乗るエレベーターには2つのボタンしかありません.UボタンはU階を上に行くボタン、DボタンはD階を下に行くボタンです.(U階の上やD階の下のフロアがなければエレベーターは動かない)
もし江湖がG階に着くならば、1つのプログラムを編纂して、少なくとも何回ボタンを押すことを求めます.エレベーターでG階まで行けない場合は「use the sta階段」を出力します.

入力

1行目はF,S,G,U,Dである.(1≦S,G≦F≦100000,0≦U,D≦100000)建物は1階から始まり、一番高いのはF階です.

しゅつりょく

第1行は江湖がS層からG層まで必要なボタン数の最大値を出力する.エレベーターに移動できない場合は「use the sta階段」を出力します.

に答える

これは基本的なBFS問題です.
出力が最高値であるため、boolean visuateを設定して重複値を除去します.
また、q値の私のリックタイプをint配列としてcount値を挿入し、if文であればcount+1!

Code

import java.io.*;
import java.util.*;

public class Main {
	static Queue<int[]> q=new LinkedList<int[]>();
	static int f,s,g,u,d;
	static boolean[] visited;
	static int answer=0;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		f=Integer.parseInt(st.nextToken());
		s=Integer.parseInt(st.nextToken());
		g=Integer.parseInt(st.nextToken());
		u=Integer.parseInt(st.nextToken());
		d=Integer.parseInt(st.nextToken());
		visited=new boolean[f+1];
		
		if(s==g)
		{
			System.out.println(0);
			return;
		}
		
		BFS(s,0);
		
		if(answer!=0)
			System.out.println(answer);
		else
			System.out.println("use the stairs");
		
    }
	
	public static void BFS(int num, int count)
	{
		q.add(new int[] {num,count});
		visited[num]=true;
		
		while(!q.isEmpty())
		{
			int now[]=q.poll();
			int nownum=now[0];
			int nowcount=now[1];
			
			if(nownum==g)
			{
				answer=nowcount;
				return ;
			}
			
			if(nownum+u <= f && !visited[nownum+u] && u!=0)
			{
				visited[nownum+u]=true;
				q.add(new int[] {nownum+u, nowcount+1});
			}
			
			if(nownum-d >=1 && !visited[nownum-d] && d!=0)
			{
				visited[nownum-d]=true;
				q.add(new int[] {nownum-d, nowcount+1});
			}
			
		}
		
	}
}