Lunedì quiz 4–soluzione
1: using System;
2: using System.Collections.Generic;
3: using System.Linq;
4: using System.Text;
5:
6: namespace Paroliere
7: {
8: class Program
9: {
10: struct Point
11: {
12: public int X;
13: public int Y;
14: }
15:
16: static string [] grid = new string [] {
17: "SZAULE" ,
18: "FURAUJ" ,
19: "EOZZUA" ,
20: "LUOAEZ" ,
21: "OIUYTA" ,
22: "RCAYKU" };
23:
24: static void Main(string [] args)
25: {
26: var s = "" ;
27: do
28: {
29: Console .WriteLine("Gimme word" );
30: s = Console .ReadLine();
31: SearchWord(s);
32: }
33: while (s.Length > 0);
34: }
35:
36: static void SearchWord(string word)
37: {
38: var result = SearchWordRecursive(word);
39: if (result.Count > 0)
40: {
41: Console.WriteLine("Word found. Coords:" );
42: foreach (var p in result[0])
43: {
44: Console .WriteLine("(X={0}, Y={1})" ,
p.X + 1, p.Y + 1);
45: }
46: }
47: else
48: {
49: Console .WriteLine("word was not found" );
50: }
51: }
52:
53: static List<List<Point>> SearchWordRec(string word)
54: {
55: var results = new List <List <Point >>();
56: if (word.Length == 1)
57: {
58: char c = word[0];
59: for (int y = 0; y < grid.Length; y++)
60: {
61: var s = grid[y];
62: for (int x = 0; x < s.Length; x++)
63: {
64: if (s[x] == c)
65: {
66: var singlePoint =
new List <Point >();
67: singlePoint.Add(new Point ()
{ X = x, Y = y });
68: results.Add(singlePoint);
69: }
70: }
71: }
72: return results;
73: }
74:
75: var subWord = word.Substring(0, word.Length - 1);
76: var nestedResults = SearchWordRec(subWord);
77: var lastChar = word[word.Length - 1];
78:
79: foreach (var nested in nestedResults)
80: {
81: var lastPoint = nested[
nested.Count – 1
];
82: var candidatePos = SearchChar(lastPoint,
lastChar);
83:
84: foreach (var p in candidatePos)
85: {
86: if (nested.Contains(p))
87: {
88: continue ;
89: }
90:
91: var newResult = new List<Point>(nested);
92: newResult.Add(p);
93: results.Add(newResult);
94: }
95: }
96:
97: return results;
98: }
99:
100: static List <Point > SearchChar(Point startingPoint,
char toSearch)
101: {
102: var r = new List <Point >();
103: for (int deltaX = -1; deltaX < 2; deltaX++)
104: {
105: for (int deltaY = -1; deltaY < 2; deltaY++)
106: {
107: if ((deltaY == 0) && (deltaX == 0))
108: {
109: continue ;
110: }
111:
112: var newY = startingPoint.Y + deltaY;
113: var newX = startingPoint.X + deltaX;
114:
115: if ((newY < 0) || (newY >= grid.Length))
116: {
117: continue ;
118: }
119:
120: if ((newX < 0)||(newX >= grid[0].Length))
121: {
122: continue ;
123: }
124:
125: if (grid[newY][newX] == toSearch)
126: {
127: r.Add(new Point(){X=newX,Y= newY});
128: }
129: }
130: }
131:
132: return r;
133: }
134: }
135: }
136:
137: