3599 | 2023. 03. 01 09:37:13 | AGergo | Rácsháló gráf | csharp | Időlimit túllépés 28/50 | 569ms | 24412 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 | 29ms | 20636 KiB | |||
2 | Időlimit túllépés | 0/0 | 560ms | 4468 KiB | |||
3 | Elfogadva | 2/2 | 32ms | 21692 KiB | |||
4 | Elfogadva | 2/2 | 30ms | 21792 KiB | |||
5 | Elfogadva | 2/2 | 30ms | 22056 KiB | |||
6 | Elfogadva | 2/2 | 32ms | 22064 KiB | |||
7 | Elfogadva | 2/2 | 143ms | 22440 KiB | |||
8 | Hibás válasz | 0/2 | 143ms | 22616 KiB | |||
9 | Elfogadva | 2/2 | 143ms | 22480 KiB | |||
10 | Elfogadva | 2/2 | 59ms | 22592 KiB | |||
11 | Elfogadva | 2/2 | 143ms | 22564 KiB | |||
12 | Időlimit túllépés | 0/2 | 560ms | 5984 KiB | |||
13 | Időlimit túllépés | 0/3 | 554ms | 6460 KiB | |||
14 | Elfogadva | 3/3 | 175ms | 23200 KiB | |||
15 | Időlimit túllépés | 0/3 | 554ms | 6832 KiB | |||
16 | Hibás válasz | 0/3 | 150ms | 23940 KiB | |||
17 | Időlimit túllépés | 0/3 | 524ms | 7248 KiB | |||
18 | Elfogadva | 3/3 | 256ms | 23944 KiB | |||
19 | Hibás válasz | 0/3 | 32ms | 23768 KiB | |||
20 | Elfogadva | 3/3 | 39ms | 24412 KiB | |||
21 | Elfogadva | 3/3 | 344ms | 24228 KiB | |||
22 | Időlimit túllépés | 0/3 | 569ms | 7592 KiB |