Подготовка за изпит по C# (part 2) 2013 Tic Tac Toe задача


0

Здравейте колеги.

Следната задача ме затруднява и по конкретно самото условие:

 

Problem 2 – Tic-Tac-Toe
You all know the game called Tic-Tac-Toe. Tic-Tac-Toe is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player always starts first. The player who succeeds in placing three respective marks in a horizontal, vertical, or a diagonal row wins the game.
The following example game is won by the first player, X:
You will be given the current state of the game and your program should find:
 the number of the games from the current state that end with a win for the first player (X),
 the number of the games from the current state that end with no winner and
 the number of the games from the current state that end with a win for the second player (O).
Input
The input data should be read from the console.
The current state of the game will be written in the console in 3 lines with exactly 3 symbols, each representing one of the nine cells of the current state of the game with ‘X’, ‘O’ (capital Latin letter O) and ‘–’ (dash) – for the empty cells. See the examples below.
The input data will always be valid and in the format described. There is no need to check it explicitly.
Output
The output data should be printed on the console.
On the first output line you should print the number of the games that the first player (X) is going to win.
On the second line you should print the number of the even games.
And on the third output line you should print the number of the games that the player O is going to win.
Constraints
 The input data will always be a valid Tic-Tac-Toe game state where the player X starts first.
 Allowed working time for your program: 0.2 seconds.
 Allowed memory: 16 MB.
Examples
Input example
Output example
O O -
X X O
X X O
1
0
0
Input example
Output example
O O -
X  -  X
-   -   -
32
0
35
 
Първия пример е пределно ясен, но втория ме обърка тотално. При него може да се получи равенство при следното развитие:
O O X
X O X
X X O
А в примера няма игра, която да завършва с равенство. Също така ме объркват и многото игри при които печелят играчите. Трудно ми е да ги докарам до 10-15 да не говорим за над 30. Всякакви идеи и разяснения са добре дошли.



Отговори



0

За примера си напълно прав/а, че случаят е пропуснат, така че не знам и отговорът дали е верен..(останалите 2 числа)

За "докарването" - разгледай задачите за пермутации, вариации и комбинации от домашното за масиви, ето в тази тема има и поствани решения. В случая търсиш всички възможни комбинации, с които елементите от входа са на съответните си места.

Предполагам намираш по-малко решения ето заради това: Да вземем примера с равенство, който ти си дал/а. Един случай е играчът X да постави Х горе вдясно, след това най-долу посредата, друг случай е да постави Х долу посредата, след това горе вдясно. Познах ли? За да го видиш нагледно може би било удобно да заместиш символите с числа - Х да поставя числа по-малки от 10, а О да поставя числа, по-големи от 10, след това намираш всички възможности и изследваш имаш ли ред/колонка/диагонал с еднакви(всички да са по-малки или всички да са по-големи от 10). Предполагам не е най-добрият вариант, но това ми хрумва на момента, не съм решавала задачата.


от spareva (1375 точки)


1
Колеги събудете се ;) има три кръгчета по диагонала горе ляво долу дясно, т.е. кръгчетата печелят. Задачата се решава с рекурсия според мен като пазиш полето в някакъв страничен масив и играеш. И след всеки ход проверяваш дали някой печели.
Трябва да внимаваш да поставяш ход след ход защото може да стигнеш до тази ситуация да печелят и двамата. Ето пример:
О О О
Х Х Х
- - -,
т.е. като поставиш Х в средата трябва да спреш функцията и да отброиш победа за Х. Аз все още я боря тази задача, но определено е по-лесна от "судоку"-то.

от makmidov (598 точки)


0
Аз пък си мисля че тази е по трудна от судоку-то. Макар че точно сега докато пишех и ми дойде идея за тази задача :) ако стане така значи е по лесна ще пробвам и ще споделя.

от nikola76 (1250 точки)


2

http://pastebin.com/G5cRRDDN

Колеги ето моето решение, което дава 100/100 в системата. В момента бързам и нямам време да давам обяснения, но се надявам да ви помогне в решаването. Можете да дебъгнете моя код, за да проследите логиката.

И не че нещо ама това:

O O X
X O X
X X O
 
е чиста победа за втория играч (О), погледни главния диагонал :D
 
За мен задачата е по-трудна от Судоку-то. Поне повече ме изпоти, нищо, че уж е само 3х3 пък онова е 9х9...

от ivaylo.kenov (30760 точки)


0
Test 1
OOX
XXO
O--
The X player always starts first. тексто от условието. Общо игрите са 126 в една игра може ли да има повече от една победа. Как се получават отоговор от тест 7
14232
5184
10176
Тази задача ако може някой да ми обясни тея два теста много ще се радвам. 

от bgpa4o (20 точки)


0
Входа на тест 7 е следният:
-X- --- ---
Тук се вижда колко много решения може да има.
Представи си лабиринт само с една попълнена клетка, да се намерят всички пътища - много са. :>

от martin.nikolov (4535 точки)


0

Задачката е доста интересна, но е трудна за проследяване и дебъгване. Бях се заблудил, че при всеки тест първи на ход е X спрямо дадената позиция, а всъщност X е първи на ход спрямо началото на играта.

Решението ми е рекурсивно. Дефинирам клас Board, който пази в char[,] Cells състоянието на дъската и едно пропърти FreePostions, което се ъпдейтва след всеки ход. В началото проверявам дали в дадената позиция има победител. След това проверявам дали са останали празни полета. Ако не, значи играта е равен. Следва рекурсивно BFS извикване на същия метод, като този, който е наред заема последователно всички възможни празни полета. При рекурсивното извикване се подава на ход другия играч. След рекурсивното извикване трябва да се възстанови състоянието - да се освободи полето, да се върне играча на ход и да се увеличи брояча на празни полета.

Резултатите пазя в едно дикшънъри <string, int> за "X", "O" и "Draw".

Решение


от AntonPetrov (654 точки)


3

Направо не мога да повярвам колко стегнато и малко се получи :) Гледах горните решения и направо се бях отчаял че ще се оплета като пате в кълчища от логика... а се получи една мъничка красота:

http://pastebin.com/cAKgULaC

1/3 от програмата ми е входа на данните, 1/3 ми е една гиганска логическа конструкция която определя дали има победител, и цялата логика се събра в 10-тин реда процедура.

Хитринката която си позволих е да работя с "дигитализирана" игрална дъска. Ползвам 0 за "Х", 1 за "О" и 2 за "-". Другото което направих за да опростя логиката е да ползвам едномерен масив - и без това почти всички операции са "изброителни", без да се интересуват много-много от редове и колони - но пък обикалянето на дъската става само с един for цикъл.

Следя за изход от рекурсията с отделен брояч, който помни колко полета са запълнени. Така и така ги пълня с входни данни, в рекурсията ми остава само да правя ++ и --. Стигна ли 9 без да съм намерил победител - резултата е "равен".

100/100 от първо пускане в bgcoder, с време 38.0859 мсек на 10-ти тест (най-тежкия).


от JulianG (5316 точки)


0
Гениално решение! Много по-кратко и елегантно от авторското, което е 200 реда.

от neutrino (3376 точки)