Zadatak Padajuce Loptice

Svi test primeri mi rade osim poslednjeg koji je RTE, pa ako bi neko ko ima pristup test primerima mogao da posalje poslednji, bio bih veoma zahvalan!

Link ka zadatku:Petlja

1 Like

Zdravo,

Vidim da su autori Zbirke namerno ostavili ovaj zadatak tako da se ne vide ni rešenje ni test primeri. Jel bi mogao ovde da postuješ kod koji submituješ pa da ti pomognemo oko debug-a?

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.SymbolStore;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Net.WebSockets;
using System.Runtime.InteropServices;
using System.Runtime.InteropServices.WindowsRuntime;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;
using System.Xml;
using System.Xml.Schema;
using System.Numerics;
//using System.Data;
//using System.Drawing;

namespace ConsoleApplication2
{
    class Program
    {
        static bool mozene(List<string> a, int m, int n, ref Dictionary<string, bool> d)
        {
            if (m < 0 || n < 0 || n >= a[0].Length || m >= a.Count)
                return false;
            string key = m.ToString() + "|" + n.ToString();
            if(!d.ContainsKey(key))
            { 
                if (a[m][n] == '.' && m == a.Count - 1)
                    return true;
                else if (a[m][n] == 'x')
                    return false;
                else if (a[m + 1][n] == 'x')
                {
                    d[key] = mozene(a, m, n - 1, ref d);
                    d[key] = d[key] || mozene(a, m, n + 1, ref d);
                }
                else if (a[m + 1][n] == '.')
                {
                    d[key] = mozene(a, m + 1, n, ref d);
                }
            }
            return d[key];
        }
        static void Main(string[] args)
        {
            List<string> a = new List<string>();
            string o;
            while ((o = Console.ReadLine()) != null)
            {
                o = o.Trim();
                a.Add(o);
            }
            int m = 0;
            string s = "";
            Dictionary<string, bool> d = new Dictionary<string, bool>();
            for (int i = 0; i < a[0].Length; i++)
            {
                if (a[0][i] == 'x')
                {
                    s += "0";
                    continue;
                }
                else
                {
                    if (mozene(a, m, i, ref d))
                        s += "1";
                    else s += "0";
                }
            }
            Console.WriteLine(s);

        }
    }
}

Evo koda, trebalo bi da sve radi, mozda je neka greska u test primeru.

RTE koji se dešava na poslednjem primeru je prekoračenje steka (stack overflow). Putanja od vrha do dna matrice u tom primeru je preduga za ovo rešenje memoizacijom. Rešenje možeš da modifikuješ ubacivanjem while petlji u rekurzivnu funkciju, tako da svaki novi poziv ide na niži red, pa bi dubina steka bila jednaka broju redova matrice (to bi trebalo da prođe).

Još bolje i čistije rešenje je dinamičkim programiranjem naviše.

2 Likes