7894 | 2024. 01. 11 18:20:34 | czita | Rácsháló gráf | csharp | Elfogadva 50/50 | 153ms | 26484 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();
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 35ms | 22232 KiB | |||
2 | Elfogadva | 0/0 | 153ms | 22896 KiB | |||
3 | Elfogadva | 2/2 | 32ms | 23160 KiB | |||
4 | Elfogadva | 2/2 | 32ms | 23708 KiB | |||
5 | Elfogadva | 2/2 | 32ms | 23928 KiB | |||
6 | Elfogadva | 2/2 | 32ms | 23696 KiB | |||
7 | Elfogadva | 2/2 | 45ms | 24212 KiB | |||
8 | Elfogadva | 2/2 | 45ms | 24028 KiB | |||
9 | Elfogadva | 2/2 | 45ms | 24252 KiB | |||
10 | Elfogadva | 2/2 | 35ms | 24384 KiB | |||
11 | Elfogadva | 2/2 | 43ms | 24748 KiB | |||
12 | Elfogadva | 2/2 | 118ms | 25000 KiB | |||
13 | Elfogadva | 3/3 | 87ms | 25468 KiB | |||
14 | Elfogadva | 3/3 | 45ms | 25088 KiB | |||
15 | Elfogadva | 3/3 | 86ms | 25268 KiB | |||
16 | Elfogadva | 3/3 | 43ms | 25396 KiB | |||
17 | Elfogadva | 3/3 | 75ms | 25736 KiB | |||
18 | Elfogadva | 3/3 | 43ms | 25540 KiB | |||
19 | Elfogadva | 3/3 | 32ms | 25412 KiB | |||
20 | Elfogadva | 3/3 | 32ms | 26100 KiB | |||
21 | Elfogadva | 3/3 | 48ms | 26484 KiB | |||
22 | Elfogadva | 3/3 | 153ms | 25544 KiB |