/************************************************ Grundlegende Algorithmen mit Java, http://algorithmen-und-problemloesungen.de/ Copyright @2007-2009 by Doina Logofatu in C#: Michael Gärtner ************************************************/ using System; using System.Collections.Generic; using System.IO; namespace Logofatu { class P10Ball { private static String FileInputName = "ball.in"; private static String FileOutputName = "ball.out"; private static bool onTheBorder(int k, int m, int n) { int l = k / n; int c = k % n; bool flag = false; if ( 0 == l || m - 1 == l ) flag = true; if ( 0 == c || n - 1 == c ) flag = true; return flag; } private static bool onTheTable(int line, int col, int m, int n) { return (0 <= line && line < m) && (0 <= col && col < n); } public static void writeSolution(List x, int[,] T, int n, StreamWriter sw) { for ( int i = 0; i < x.Count; i++ ) { sw.Write('('); sw.Write(x[i] / n + 1); sw.Write(", "); sw.Write(x[i] % n + 1); sw.Write(") "); } sw.WriteLine(); } private static void back(List x, int[,] T, int m, int n, StreamWriter sw) { int k = x.Count - 1; int xk = x[k]; if ( onTheBorder(xk, m, n) ) { writeSolution(x, T, n, sw); return; } int l = xk / n; int c = xk % n; int lnew, cnew, dx, dy; for ( dx = -1; dx < 2; dx++ ) for ( dy = -1; dy < 2; dy++ ) if ( 1 == Math.Abs(dx + dy) ) { lnew = l + dx; cnew = c + dy; if ( onTheTable(lnew, cnew, m, n) && T[lnew, cnew] < T[l, c] ) { x.Add(lnew * n + cnew); back(x, T, m, n, sw); x.RemoveAt(x.Count - 1); } } } static void Main(string[] args) { StreamReader sr = null; StreamWriter sw = null; try { sw = new StreamWriter(FileOutputName); sr = new StreamReader(FileInputName); string[] sArray = sr.ReadLine().Split(' '); int m = int.Parse(sArray[0]); int n = int.Parse(sArray[1]); int[,] t = new int[m, n]; for ( int i = 0; i < m; i++ ) { sArray = sr.ReadLine().Split(' '); for ( int j = 0; j < n; j++ ) t[i, j] = int.Parse(sArray[j]); } sArray = sr.ReadLine().Split(' '); int l0 = int.Parse(sArray[0]) - 1; int c0 = int.Parse(sArray[1]) - 1; List x = new List(); x.Add(l0 * n + c0); back(x, t, m, n, sw); } catch ( IOException ex ) { Console.WriteLine("Fehler bei der Dateiverarbeitung!\n" + ex.ToString()); } finally { if ( sr != null ) { sr.Close(); } if ( sw != null ) { sw.Close(); } } } } }