78942024-01-11 18:20:34czitaRácsháló gráfcsharpAccepted 50/50153ms26484 KiB
using System;
using System.Linq;

namespace racshalo
{
    
    class Program
    {
        
        static void Main(string[] args)
        {
            #region beolvasas alapadatok
            int[] st = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = st[0];
            int M = st[1];
            int K = st[2];
            #endregion
            int[,] graf = new int[N * M + 1, N * M + 1];//n*m-es éllistás gráf létrehozása i,j a pontok sorszáma
            //egy sorral oszlopppal nagyobb, hogy ne legyen probléma a 0 index
            for (int i = 1; i <= N * M; i++)//végig a sorokon oszlopokon 1-től indukl a 0 sort oszlopot nem figyeli
            {
                for (int j = 1; j <= N * M; j++)
                {
                    if (i != j)
                    {
                        graf[i, j] = N*M+10;//ahol pont nem önmagába mutat i!=j ott kap egy a távolságnál nagyobb számot, ennél találni lehet kisebbet
                    }
                }
            }
            //a szomszédpontok beállítása
            int aktpont = 0, felette = 0, alatta = 0, jobbra = 0, balra = 0;//a szomszédpontok helye a gráfban

            for (int i = 1; i <= N; i++)//végig sorokon oszlopokon
            {
                for (int j = 1; j <= M; j++)
                {
                    aktpont = (i - 1) * M + j;//aktuális pont meghatározása M=4 2 sor 1 pont 5 számot kap
                    felette = aktpont-M;//egy sorral kevesebb
                    alatta = aktpont+M;//egy sorral több
                    jobbra = aktpont+ 1;//egyet több
                    balra = aktpont - 1;//egyel kevesebb

                    if (i == 1)//első sorm nincs felette semmi
                    {
                        felette = 0;//nullás sorra teszi, ami nem veszünk figylemebe
                    }
                    else if (i == N)//utolsĂł sor nincs alatta semmi
                    {
                        alatta = 0;
                    }
                    if (j == 1)//nincs tĂłle balra semmi
                    {
                        balra = 0;
                    }
                    else if (j == M)//utolsĂł oszlop nincs jobbra semmi
                    {
                        jobbra = 0;
                    }
                    //az aktuális pont és a szomszádai távolságát 1-re állítjuk
                    graf[jobbra, aktpont] = 1;
                    graf[alatta, aktpont] = 1;
                    graf[aktpont, jobbra] = 1;
                    graf[aktpont, alatta] = 1;
                }
            }
            //legrövidebb utak kiszámítása minden pontból minden pontra
            //Floy Warshall algoritmus
            for (int k = 1; k <= N * M; k++)
            {
                for (int i = 1; i <= N * M; i++)
                {
                    for (int j = 1; j <= N * M; j++)
                    {
                        if (graf[i, j] > graf[i, k] + graf[k, j])//ha az aktuális két pont távolsága nagyobb, mintha két másik pontbül érnénk el
                        {
                            graf[i, j] = graf[i, k] + graf[k, j];//ez lesz az új rövidebb távolság
                        }
                    }
                }
            }
            string ki = "";//ezt fogja kiĂ­rni
            for (int cv = 0; cv < K; cv++)//végimegyünk a felveendő pontokon
            {
                st = Console.ReadLine().Split().Select(int.Parse).ToArray();//pontok beolvasása
                graf[st[0], st[1]] = 1;
                graf[st[1], st[0]] = 1;
                //elég csak erre a két pontra meghatározni a többi távolságát
                int k = st[0];//egyik pont
                for (int i = 1; i <= N * M; i++)//csak két ciklus
                {
                    for (int j = 1; j <= N * M; j++)
                    {
                        if (graf[i, j] > graf[i, k] + graf[k, j])//keres egy rövidebb távolságot
                        {
                            graf[i, j] = graf[i, k] + graf[k, j];
                        }
                    }
                }
                //a másik pontnál ugyanez
                k = st[1];
                for (int i = 1; i <= N * M; i++)
                {
                    for (int j = 1; j <= N * M; j++)
                    {
                        if (graf[i, j] > graf[i, k] + graf[k, j])
                        {
                            graf[i, j] = graf[i, k] + graf[k, j];
                        }
                    }
                }
                //meghatározza a mátrix leghosszabb távolságát
                int max = 0;
                for (int i = 1; i <= N*M; i++)
                {
                    for (int j = 1; j <= N*M; j++)
                    {
                        if (graf[i, j] > max )
                        {
                            max = graf[i, j];
                        }
                    }
                }
                ki += max+"\r\n";//hozzáfűzi a kiiratandókhoz
            }
            Console.Write(ki);//kiírja a legrövidebb utakat
            Console.ReadKey();
        }
    }
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/035ms22232 KiB
2Accepted0/0153ms22896 KiB
3Accepted2/232ms23160 KiB
4Accepted2/232ms23708 KiB
5Accepted2/232ms23928 KiB
6Accepted2/232ms23696 KiB
7Accepted2/245ms24212 KiB
8Accepted2/245ms24028 KiB
9Accepted2/245ms24252 KiB
10Accepted2/235ms24384 KiB
11Accepted2/243ms24748 KiB
12Accepted2/2118ms25000 KiB
13Accepted3/387ms25468 KiB
14Accepted3/345ms25088 KiB
15Accepted3/386ms25268 KiB
16Accepted3/343ms25396 KiB
17Accepted3/375ms25736 KiB
18Accepted3/343ms25540 KiB
19Accepted3/332ms25412 KiB
20Accepted3/332ms26100 KiB
21Accepted3/348ms26484 KiB
22Accepted3/3153ms25544 KiB