fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 	    List<String> towns = new ArrayList<>();
  13.         towns.add("Москва");
  14.         towns.add("Саратов");
  15.         towns.add("Свердловск");
  16.         towns.add("Астана");
  17.         towns.add("Астрахань");
  18.         towns.add("Санкт-петербург");
  19.         towns.add("Гурьев");
  20.         towns.add("Начало");
  21.         towns.add("Орёл");
  22.         towns.add("Липецк");
  23.         towns.add("Кишенёв");
  24.         towns.add("Владимир");
  25.         towns.add("Ростов");
  26.         towns.add("Воронеж");
  27.         towns.add("Житомир");
  28.         towns.add("Минск");
  29.         towns.add("Киров");
  30.         towns.add("Норильск");
  31.         towns.add("Муром");
  32.         towns.add("Донецк");
  33.         towns.add("Тьмутаракань");
  34.         towns.add("Омск");
  35.         towns.add("Каракум");
  36.         towns.add("Волгоград");
  37.         towns.add("Уфа");
  38.         towns.add("Тарту");
  39.         towns.add("Рига");
  40.         towns.add("Ю");
  41.  
  42.         int max = 0;
  43.         List<String> result = new ArrayList<>();
  44.         String resultStart = "";
  45.  
  46.         for (String town : towns) {
  47.             TownsGame.maxDepth = 0;
  48.             TownsGame.maxHead = null;
  49.             new TownsGame(null, town, towns, 0);
  50.  
  51.             if (TownsGame.maxHead != null) {
  52.                 if (max < TownsGame.maxDepth) {
  53.                     TownsGame h = TownsGame.maxHead;
  54.                     result = new ArrayList<>();
  55.                     while (h.parent != null) {
  56.                         result.add(0, h.content);
  57.                         h = h.parent;
  58.                     }
  59.                     max = TownsGame.maxDepth;
  60.                     resultStart = town;
  61.                 }
  62.             }
  63.         }
  64.  
  65.         System.out.println("[" + resultStart + "]");
  66.         for (int i = 0; i < result.size(); i++) {
  67.             System.out.print(result.get(i));
  68.             if (i < result.size() - 1) System.out.print(" -> ");
  69.         }
  70.     }
  71.  
  72.     public static class TownsGame {
  73.         final TownsGame parent;
  74.         final String content;
  75.         final List<String> usable;
  76.         final List<TownsGame> next;
  77.  
  78.         static int maxDepth = 0;
  79.  
  80.         static TownsGame maxHead;
  81.  
  82.         public TownsGame(TownsGame parent, String content, List<String> usable, int depth) {
  83.             this.parent = parent;
  84.             this.content = content;
  85.             this.usable = new ArrayList<>(usable);
  86.             this.usable.remove(content);
  87.             this.next = new ArrayList<>();
  88.             boolean nextT = false;
  89.             for (int i = 0; i < this.usable.size(); i++) {
  90.                 if (this.usable.get(i).length() < 1) continue;
  91.                 char fChar = Character.toLowerCase(this.usable.get(i).charAt(0));
  92.                 char eChar = Character.toLowerCase(content.charAt(content.length() - 1));
  93.                 if (eChar == 'ь') {
  94.                     if (content.length() < 2) continue;
  95.                     eChar = content.charAt(content.length() - 2);
  96.                 }
  97.                 if (fChar == eChar) {
  98.                     next.add(new TownsGame(this, this.usable.get(i), this.usable, depth + 1));
  99.                     nextT = true;
  100.                 }
  101.             }
  102.             if (!nextT) {
  103.                 if (depth > maxDepth) {
  104.                     maxDepth = depth;
  105.                     maxHead = this;
  106.                 }
  107.             }
  108.         }
  109.     }
  110. }
Success #stdin #stdout 0.25s 320512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[Санкт-петербург]
Гурьев -> Владимир -> Ростов -> Воронеж -> Житомир -> Рига -> Астана -> Астрахань -> Начало -> Орёл -> Липецк -> Кишенёв -> Волгоград -> Донецк -> Каракум -> Муром -> Минск -> Киров
https://ideone.com/vpmvrr
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!