Hledani nejkratsiho zpusobeni napsani slova

abeceda.cs

using System;
using System.Collections.Generic;
using CodEx;

public struct Path
{
	public int Steps; // Počet kroku pro dosazeni
	public int I; // Pozice I pri dosazeni pismene
	public int J; // Pozice J pri dosazeni pismene
}

static public class WordTyper
{
	public static int Width;
	public static int Height;

	public static char[,] LetterGrid;
	
	public static char[] Word;
	
	public static List<Path>[] Paths;
	
	public static List<Path> findNextLetter(char c, int x, int y) {
		//Console.WriteLine("Hledam pismeno {0} ze souradnice {1}:{2}", c, x, y);
		List<Path> NextLetters = new List<Path>();
		
		for (int i = 0; i < Height; i++) {
			for (int j = 0; j < Width; j++) {
				if (LetterGrid[i,j] == c) {
					NextLetters.Add(new Path {
						I = i,
						J = j,
						Steps = Math.Abs(x-i) + Math.Abs(y-j) + 1
					});
				}
			}
		}
		
		return NextLetters;
	}
	
	public static bool isLetterInGrid(char c) {
		
		for (int i = 0; i < Height; i++) {
			for (int j = 0; j < Width; j++) {
				if (LetterGrid[i,j] == c) {
					return true;
				}
			}
		}
		
		return false;
	}
	
	public static int findShortestTypingPath() {
		
		Paths = new List<Path>[Word.Length];
		
		// Inicializace prvního písmene
		List<Path> FirstPaths = WordTyper.findNextLetter(Word[0], 0, 0);
		Paths[0] = new List<Path>();
		
		for (int i = 0; i < FirstPaths.Count; i++) {
			Paths[0].Add(FirstPaths[i]);
		}		
		
		// Postupně zjistíme nejdelší cesty pro každé písmeno
		for (int i = 1; i < Word.Length; i++) {
			Paths[i] = new List<Path>();
			
			// Pokud písmeno není v gridu, jdeme na další
			if (!isLetterInGrid(Word[i])) {
				Paths[i] = Paths[i-1];
				continue;
			}
			
			// Znamená, že jsme ješte vůbec nenašli první písmeno
			if (Paths[i-1].Count == 0) {
				Paths[i-1].Add(new Path {
					I = 0,
					J = 0,
					Steps = 0,	
				});
			}
			
			// Projdeme každou z předchozích cest a přičteme k nim všechny možnosti dosažení písmene z daných pozic
			for (int j = 0; j < Paths[i-1].Count; j++) {
				
				List<Path> NextPaths = WordTyper.findNextLetter(Word[i], Paths[i-1][j].I, Paths[i-1][j].J);
				
				for(int k = 0; k < NextPaths.Count; k++) {
					Paths[i].Add(new Path{
						I = NextPaths[k].I,
						J = NextPaths[k].J,
						Steps = Paths[i-1][j].Steps + NextPaths[k].Steps
					});
				}
			}
		}
		
		// Najdeme nejkratší cestu
		int max = int.MaxValue;
		
		//Console.WriteLine("Existuje {0} zpusobu, jak napsat slovo", Paths[Word.Length-1].Count);
		foreach (Path final in Paths[Word.Length - 1]) {
			if (final.Steps < max) {
				//Console.WriteLine("Nasel jsem zpusob s {0} kliky", final.Steps);
				max = final.Steps;
			}
		}
		
		// Nenašla se žádná cesta, tzn. ani jedno z písmen ve slově nebylo v tabulce
		if (max == int.MaxValue) {
			return 0;
		}
		
		return max;
	}
	

}

public class Abeceda
{	
	
	static public void Main ()
	{
		//Console.WriteLine ("Hello Mono World");
		
		int i = Reader.Console().Int();
		int j = Reader.Console().Int();
		
		WordTyper.LetterGrid = new char[j,i];
		WordTyper.Width = i;
		WordTyper.Height = j;
		
		//Console.WriteLine("Sirka tabulky je {0}, vyska {1}", i, j);
		
		Reader.Console().Char(); // drop newline
		
		for (int k = 0; k < i * j; k++) {
			char letter = Reader.Console().Char();
			if (letter == '\r' || letter == '\n') {
				k--;
				continue;
			}
			
			WordTyper.LetterGrid[k / i, k % i] = letter;
		}
			
		string Line = Reader.Console().Word();
		
		WordTyper.Word = new char[Line.Length];
		
		for (int index = 0; index < Line.Length; index++) {
			WordTyper.Word[index] = Line[index];
		}
				
		//Console.WriteLine("\nNacteno slovo  {0}", Line);
		
		//Console.WriteLine("Nejmensi pocet tahu pro dosazeni cile je: {0}", WordTyper.findShortestTypingPath());
		Console.WriteLine("{0}", WordTyper.findShortestTypingPath());
		
	}
 
}