Здравейте, дали някой от екипа може да качи тестовете, защото на нулевите имам верен резултат, а на другите нула и започвам лекинко да се изнервям :) Другият вариант е някой колега да удари едно рамо ако му се занимава, ето кода:
Благодаря!
Ето ги тестовете: ЛИНК
По принцип за тези задачи има някаква вероятност да са ми грешни решенията, съответно тестовете, но виждам, че има хора с по 100, така че по-скоро няма грешки.
Относно задачата с най-краткия път в матрица - уточнение, което добавих в условието тези дни - ако има два пътя с еднаква дължина, избира се този, в който участват клетки, които са на по-горен ред или в по-лява колона (т.е. обхождането е стандартно по редове отгоре надолу и по колони от ляво надясно). Има няколко души с грешка на 1 тест, които връщат верен път, но просто пътят е различен от този в тестовете. Понеже в джъдж се сравнява изхода 1:1, възможно е верни решения да не минат, затова добавих това допълнително условие.
Ами не, аз се сетих къде ми е грешката, въпроса сега е да се сетя как да я оправя :D Мерси за тестовете.
Иска потребителско и парола за сървъра.
User: student
Pass: student
Може ли да дадеш линк и към тестовете за първата задача (Shortest Path in Matrix). За примерите от домашното ми върви (нулевите в judge), всички други не минават.
Благодаря предварително.
^ Имаш тайм лимити и ексепшъни, виж да не си хардкоднал някакви променливи или проверки, примерите са с еднакъв размер матрици, но в тестовете има всякакви.
IndexOutOfRangeException - това е, което виждам, би трябвало да можеш да го намериш ако изтестваш.
Ще ги кача и тези тестове по някое време.
Тестовете за задачата с матрицата са ТУК.
Мерси много. Оправих exception-а (от хардкодната стойност беше наистина). Тайм лимитите ми явно са при големите матрици, понеже използвам backtracking да обхождам матрицата и заспива програмата. Ще гледам до утре да измисля някаква оптимизация. Сега не се сещам за нищо. Мислих си за greedy подход да избира най-малката от съседните 4-ри стойности, но така пък не мисля, че ще се изчислят правилно разстоянията.
С едно обхождане по всички нодове трябва да стане, като стигнеш до някъде трябва да запазиш пътя до там. Аз го направих с клас Node, където пазя най малкото разтояние до нода, оригиналната стойност и нода от където се стига до него. Като свърши Дийкстрата можеш да получиш най-краткият път от който и да е нод до стартовия. https://github.com/IvanMladenov/Algorithms/blob/master/ProblemSolvingHomework/ShortestPathInMatrix/Program.cs
Не е най-умното нещо дето съм писал ама мисля че работи добре.
Задачата е класическо приложение на Dijkstra, просто графът е даден като матрица. На мен най-трудната част ми беше да го преобразувам като ползвах списък на съседство (защото с него най-лесно боравя, а и най-често сме ползвали май).
Ето и едно решение с матрица на съседство: http://pastebin.com/kcm8QNbC. Стори ми се по-естествено, защото имам на входа матрица и защото съм го правил вече с матрица и имам кода готов. Ако ми остане време смятам да направя и Dijkstra със списък на съседство. Но наистина преобразуването на входната матрица беше най-засуканата част - макар и доста по-кратка и лека от Dijkstra като логика.
Днеска докато преговарях лекцията за динамично оптимиране попаднах на алгоритъма за "Move Down/Right Sum" задачата. Според мен задачата за най-кратък път в матрица може да се сведе до нейна версия. Реших я по този начин, в джъдж 75/100, но нямам време да дебъгвам.
Според мен няма как да се получи така, понеже нямаш ограничение накъде може да се ходи и съответно имаш грешни отговори на няколко теста, в които дължината на пътя е по-голяма от оптималната.
В един от тестовете пък връщаш правилен отговор, но не спазваш условието за обхождане, понеже има два пътя с еднаква дължина, а за да се направи задачата тестваема трябва да минеш по точно определен от тях. Ако имаш два пътя с еднаква дължина трябва да минеш по този, който минава по клетки, които са на по-малък ред/колона.
Да, прав си. А "move down/right" поставя ограничение за движение...
С едно обхождане по всички нодове трябва да стане, като стигнеш до някъде трябва да запазиш пътя до там. Аз го направих с клас Node, където пазя най малкото разтояние до нода, оригиналната стойност и нода от където се стига до него. Като свърши Дийкстрата можеш да получиш най-краткият път от който и да е нод до стартовия. https://github.com/IvanMladenov/Algorithms/blob/master/ProblemSolvingHomework/ShortestPathInMatrix/Program.cs
Не е най-умното нещо дето съм писал ама мисля че работи добре.