Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 3 KB
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace Lampak
{
class Coords
{
public int x, y;
public Coords(int _x, int _y)
{
x = _x;
y = _y;
}
}
class Lampak
{
private int n, m;
private int k, h;
private int[,] table;
private int[,] steps;
private bool[,] alreadyOK;
private Queue<Coords> q;
private const int taskNo = 30;
public Lampak()
{
StreamReader ins = new StreamReader("lampak" + taskNo + ".in");
StreamWriter outs = new StreamWriter("lampak" + taskNo + ".out");
string[] line = ins.ReadLine().Split(' ');
n = int.Parse( line[0] );
m = int.Parse( line[1] );
k = int.Parse( line[2] );
h = int.Parse( line[3] );
table = new int[n, m];
alreadyOK = new bool[n, m];
steps = new int[n, m];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
table[i, j] = 1;
alreadyOK[i, j] = false;
steps[i, j] = -1;
}
}
int x, y, db = n*m;
int w = ((h-1)/2);
for (int i = 0; i < k; i++)
{
line = ins.ReadLine().Split(' ');
x = int.Parse( line[0] )-1;
y = int.Parse( line[1] )-1;
for (int j = x - w; j <= x + w; j++)
{
for (int l = y - w; l <= y + w; l++)
{
if (j >= 0 && l >= 0 && j < n && l < m)
{
if (table[j, l] == 1) db--;
table[j, l] = 0;
}
}
}
}
outs.WriteLine(db);
dijkstra();
outs.WriteLine( steps[n-1, m-1] );
outs.Close();
}
private void dijkstra()
{
q = new Queue<Coords>();
q.Enqueue( new Coords(0, 0) );
steps[0, 0] = table[0, 0];
Coords c;
while (q.Count != 0)
{
c = q.Dequeue();
alreadyOK[c.x, c.y] = true;
check( c.x+1, c.y, steps[c.x, c.y] );
check( c.x, c.y+1, steps[c.x, c.y] );
check( c.x-1, c.y, steps[c.x, c.y] );
check( c.x, c.y-1, steps[c.x, c.y] );
}
}
private void check(int x, int y, int v)
{
if (x >= 0 && y >= 0 && x < n && y < m)
{
if (alreadyOK[x, y]) return;
if (steps[x, y] == -1)
{
q.Enqueue( new Coords(x, y) );
}
if ( steps[x, y] == -1 || steps[x, y] > v + table[x, y])
{
steps[x, y] = v + table[x, y];
}
}
}
static void Main(string[] args)
{
new Lampak();
}
}
}
