3592 | 2023. 03. 01 09:28:43 | AGergo | Rácsháló gráf | csharp | Időlimit túllépés 28/50 | 580ms | 24844 KiB |
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace graf
{
class Program
{
static void Main(string[] args)
{
string[] be = Console.ReadLine().Split();
int n = int.Parse(be[0]);
int m = int.Parse(be[1]);
int k = int.Parse(be[2]);
int[,] dist = new int[n * m + 1, n * m + 1];
for (int i = 1; i < n*m+1; i++)
{
for (int j = 1; j < n * m+1; j++)
{
dist[i, j] = 201;
}
}
int down = 0;
int up = 0;
int left = 0;
int right = 0;
for (int i = 1; i < n*m+1; i++)
{
if ((i-1)/m == 0)
{
up = 0;
down = i + m;
}
else if ((i-1)/m == n-1)
{
up = i - m;
down = 0;
}
else
{
up = i - m;
down = i + m;
}
if (i % m == 1)
{
left = 0;
right = i + 1;
}
else if (i % m == 0)
{
left = i - 1;
right = 0;
}
else
{
left = i - 1;
right = i + 1;
}
//Console.WriteLine(i + "-" + up + " " + down + " " + left + " " + right);
dist[i, up] = 1;
dist[up, i] = 1;
dist[i, down] = 1;
dist[down, i] = 1;
dist[i, left] = 1;
dist[left, i] = 1;
dist[i, right] = 1;
dist[right, i] = 1;
}
int largest = 0;
List<int> ll = new List<int>();
for (int i = 0; i < k; i++)
{
largest = 0;
be = Console.ReadLine().Split();
dist[int.Parse(be[0]), int.Parse(be[1])] = 1;
dist[int.Parse(be[1]), int.Parse(be[0])] = 1;
for (int sta = 1; sta < n*m+1; sta++)
{
for (int end = 1; end < n*m+1; end++)
{
for (int koz = 1; koz < n*m+1; koz++)
{
if (sta == end || dist[sta,end] == 1)
{
break;
}
if (dist[sta,end] > dist[sta,koz] + dist[koz, end]) //problema -> előbb nezi meg d[4,9]-t mint
{
dist[sta, end] = dist[sta, koz] + dist[koz, end];
dist[end, sta] = dist[sta, koz] + dist[koz, end];
}
}
}
}
for (int x = 1; x < n*m+1; x++)
{
for (int y = x + 1; y < n*m+1; y++)
{
if (dist[x,y] > largest)
{
largest = dist[x, y];
}
}
}
//Console.WriteLine(largest);
ll.Add(largest);
}
foreach (var item in ll)
{
Console.WriteLine(item);
}
Console.ReadLine();
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 28/50 | ||||||
1 | Elfogadva | 0/0 | 28ms | 20700 KiB | |||
2 | Időlimit túllépés | 0/0 | 575ms | 4548 KiB | |||
3 | Elfogadva | 2/2 | 30ms | 21932 KiB | |||
4 | Elfogadva | 2/2 | 32ms | 22272 KiB | |||
5 | Elfogadva | 2/2 | 32ms | 22684 KiB | |||
6 | Elfogadva | 2/2 | 32ms | 22372 KiB | |||
7 | Elfogadva | 2/2 | 134ms | 22724 KiB | |||
8 | Hibás válasz | 0/2 | 133ms | 22780 KiB | |||
9 | Elfogadva | 2/2 | 134ms | 22872 KiB | |||
10 | Elfogadva | 2/2 | 57ms | 22884 KiB | |||
11 | Elfogadva | 2/2 | 134ms | 23244 KiB | |||
12 | Időlimit túllépés | 0/2 | 564ms | 7076 KiB | |||
13 | Időlimit túllépés | 0/3 | 555ms | 6816 KiB | |||
14 | Elfogadva | 3/3 | 165ms | 23800 KiB | |||
15 | Időlimit túllépés | 0/3 | 577ms | 7460 KiB | |||
16 | Hibás válasz | 0/3 | 140ms | 24696 KiB | |||
17 | Időlimit túllépés | 0/3 | 580ms | 7836 KiB | |||
18 | Elfogadva | 3/3 | 238ms | 24424 KiB | |||
19 | Hibás válasz | 0/3 | 34ms | 24784 KiB | |||
20 | Elfogadva | 3/3 | 39ms | 24844 KiB | |||
21 | Elfogadva | 3/3 | 321ms | 24648 KiB | |||
22 | Időlimit túllépés | 0/3 | 565ms | 8400 KiB |