/************************************************ Grundlegende Algorithmen mit Java, http://algorithmen-und-problemloesungen.de/ Copyright @2007-2008 by Doina Logofatu in C#: Michael Gärtner ************************************************/ using System; using System.IO; namespace Logofatu { public class P03Knight { private static String FileInputName = "springer.in"; private static String FileOutputName = "springer.out"; private static int[] dx = { -2, -2, -1, -1, 1, 1, 2, 2 }; private static int[] dy = { -1, 1, -2, 2, -2, 2, -1, 1 }; private static bool onTheTable(int x, int y, int m, int n) { return (0 <= x && x < m) && (0 <= y && y < n); } private static int nrAllowedSteps(int[,] a, int m, int n, int x, int y) { int nr = 0; int xn, yn; for ( int i = 0; i < 8; i++ ) { xn = x + dx[i]; yn = y + dy[i]; if ( onTheTable(xn, yn, m, n) && a[xn, yn] == 0 ) { nr++; } } return nr; } private static bool findBestSucc(int[,] a, int m, int n, int[] xy) { int aux = int.MaxValue; int xn, yn, xx = 0, yy = 0; for ( int i = 0; i < 8; i++ ) { xn = xy[0] + dx[i]; yn = xy[1] + dy[i]; if ( onTheTable(xn, yn, m, n) && a[xn, yn] == 0 ) { int steps = nrAllowedSteps(a, m, n, xn, yn); if ( steps < aux ) { aux = steps; xx = xn; yy = yn; } } } if ( aux < int.MaxValue ) { xy[0] = xx; xy[1] = yy; return true; } return false; } static void Main(string[] args) { StreamReader sr = null; StreamWriter sw = null; try { sr = new StreamReader(FileInputName); sw = new StreamWriter(FileOutputName); string[] sArray; sArray = sr.ReadLine().Split(' '); int m = int.Parse(sArray[0]); int n = int.Parse(sArray[1]); sArray = sr.ReadLine().Split(' '); int l = int.Parse(sArray[0]); int c = int.Parse(sArray[1]); l--; c--; int[,] a = new int[m, n]; a[l, c] = 1; int ctr = 1; int[] xy = new int[2]; xy[0] = l; xy[1] = c; while ( findBestSucc(a, m, n, xy) ) { a[xy[0], xy[1]] = ++ctr; } if ( ctr == m * n ) { for ( int i = 0; i < m; i++ ) { for ( int j = 0; j < n; j++ ) { sw.Write("{0,4:D}", a[i, j]); } sw.WriteLine(); } } else { sw.WriteLine("Keine Loesung!"); } } catch ( IOException ) { Console.WriteLine("Fehler bei der Dateiverarbeitung!"); } finally { if ( sr != null ) { sr.Close(); } if ( sw != null ) { sw.Close(); } } } } }