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