3585 | 2023. 03. 01 09:14:00 | gergo | Rácsháló gráf | csharp | Elfogadva 50/50 | 144ms | 26792 KiB |
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace racshalograf
{
class Program
{
static void Main(string[] args)
{
int[] bemenet = Console.ReadLine().Split().Select(int.Parse).ToArray();
int n = bemenet[0], m = bemenet[1], h = bemenet[2];
int csucsok = n * m;
int[,] matrix = new int[csucsok+1, csucsok+1];
for (int i = 1; i <= csucsok; i++)
{
for (int j = 1; j <= csucsok; j++)
{
if (i!=j) matrix[i, j] = n+m;
}
}
for (int i = 1; i <= n; i++) // (i-1)*m+j
{
for (int j = 1; j <= m; j++)
{
int aktpont = (i - 1) * m + j;
int jobbra = aktpont + 1;
int balra = aktpont - 1;
int felette = aktpont - m;
int alatta = aktpont + m;
if (i == 1) felette = 0;
if (i == n) alatta = 0;
if (j == 1) balra = 0;
if (j == m) jobbra = 0;
matrix[aktpont, jobbra] = 1;
matrix[jobbra, aktpont] = 1;
matrix[alatta, aktpont] = 1;
matrix[aktpont, alatta] = 1;
}
}
//for (int i = 0; i < csucsok; i++)
//{
// for (int j = 0; j < csucsok; j++)
// {
// Console.Write(matrix[i, j] + "\t");
// }
// Console.WriteLine();
//}
for (int k = 1; k <= csucsok; k++) //Floyd-Warshall algoritmus
{
for (int i = 1; i <= csucsok; i++)
{
for (int j = 1; j <= csucsok; j++)
{
if (matrix[i,j]>matrix[i,k]+matrix[k,j])
{
matrix[i, j] = matrix[i,k] + matrix[k,j];
}
}
}
}
string ki = "";
for (int cv = 0; cv < h; cv++)
{
bemenet = Console.ReadLine().Split().Select(int.Parse).ToArray();
matrix[bemenet[0], bemenet[1]] = 1;
matrix[bemenet[1], bemenet[0]] = 1;
int k = bemenet[0];
for (int i = 1; i <= csucsok; i++)
{
for (int j = 1; j <= csucsok; j++)
{
if (matrix[i,j] > matrix[i,k] + matrix[k,j])
{
matrix[i, j] = matrix[i,k] + matrix[k,j];
}
}
}
k = bemenet[1];
for (int i = 1; i <= csucsok; i++)
{
for (int j = 1; j <= csucsok; j++)
{
if (matrix[i, j] > matrix[i,k] + matrix[k,j])
{
matrix[i, j] = matrix[i,k] + matrix[k,j];
}
}
}
int max = 0;
for (int i = 1; i <= csucsok; i++)
{
for (int j = 1; j <= csucsok; j++)
{
if (matrix[i, j] > max) max = matrix[i, j];
}
}
ki += max + "\r\n";
}
Console.WriteLine(ki);
Console.ReadKey();
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 32ms | 22508 KiB | |||
2 | Elfogadva | 0/0 | 143ms | 22940 KiB | |||
3 | Elfogadva | 2/2 | 32ms | 23136 KiB | |||
4 | Elfogadva | 2/2 | 32ms | 23252 KiB | |||
5 | Elfogadva | 2/2 | 34ms | 23676 KiB | |||
6 | Elfogadva | 2/2 | 32ms | 23828 KiB | |||
7 | Elfogadva | 2/2 | 43ms | 24096 KiB | |||
8 | Elfogadva | 2/2 | 43ms | 24108 KiB | |||
9 | Elfogadva | 2/2 | 43ms | 24540 KiB | |||
10 | Elfogadva | 2/2 | 35ms | 24780 KiB | |||
11 | Elfogadva | 2/2 | 41ms | 25312 KiB | |||
12 | Elfogadva | 2/2 | 112ms | 25716 KiB | |||
13 | Elfogadva | 3/3 | 82ms | 25616 KiB | |||
14 | Elfogadva | 3/3 | 43ms | 25380 KiB | |||
15 | Elfogadva | 3/3 | 79ms | 25500 KiB | |||
16 | Elfogadva | 3/3 | 45ms | 25668 KiB | |||
17 | Elfogadva | 3/3 | 70ms | 25944 KiB | |||
18 | Elfogadva | 3/3 | 43ms | 26192 KiB | |||
19 | Elfogadva | 3/3 | 32ms | 26296 KiB | |||
20 | Elfogadva | 3/3 | 34ms | 26792 KiB | |||
21 | Elfogadva | 3/3 | 45ms | 26624 KiB | |||
22 | Elfogadva | 3/3 | 144ms | 26600 KiB |