===== Dark streets =====
**Zadání**\\
Viz odkaz: [[http://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=darkstreets|Neosvětlené ulice]].\\
**Schéma řešení**\\
1. Průchod do šiřky (BFS)\\
Podle zadání rozumíme vzdáleností dvou křižovatek nejmenší možný počet neosvětlených (černých) hran na cestě mezi nimi. Do obyčejné fronty (označené jako černá fronta) si tedy budeme ukládat, jako vždy v BFS, postupně uzly ve vzdálenosti 0, 1, 2, atd. od výchozí křižovatky. Kdykoli odebereme křižovatku X z čela černé fronty, uložíme na konec černé fronty všechny křižovatky Y, které sousedí s X a ulice (X Y) je neosvětlená (černá). Pokud některá Y sousedí s další křižovatkou Z a přitom ulice (Y Z) je osvětlená (bílá), vložíme na konec černé fronty také všechny křižovatky W, do kterých se lze dostat z Y pouze použitím osvětlených (bílých) ulic a ze kterých vede černá ulice. Všechny tyto křižovatky W mají totiž od X jednotkovou vzdálenost, tudíž i také mají od startovní křižovatky stejnou vzdálenost, jako má Y od startovní křižovatky, a patří tedy na aktuální konec černé fronty. Nalezení všech potřebných křižovatek W provedeme opět pomocí standardního BFS, musíme mít jen jinou frontu, v kódu je označena jako bílá.\\
Při navštěvování a probírání dalších křižovatek, uvažujeme vždy jen křižovatky dosud nenavštívené (které dosud nebyly ani v černé ani v bílé frontě), jak je to ostatně v BVS zcela obvyklé.
Pokud startovní křižovatka sousedí s osvětlenou ulicí, prohledáme nejprve osvětlenou oblast, v níž se nachází, s pomocí bílé fronty.\\
Jakmile při práci v kterékoli frontě narazíme na cílovou křižovatku, končíme.\\
Ulice jsou uloženy ve 3D poli, první dvě dimenze určují souřadnice křižovatky, ve třetí dimenzi jsou
uloženy čtyří logické hodnoty, určující, zda vede osvětlená nebo neosvětlená ulice z této křižovatky na východ, sever, západ, jih. Každá ulice je tak reprezentována dvakrát, v obou svých krajních křižovatkách. Lze uvažovat i o jiných a úspornějších reprezentacích, tato byla zvolena pro svou relativní intuitivní přehlednost.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Example{
static int M, N, L;
static int EAST=0, NORTH=1, WEST=2, SOUTH=3; // indices of directions
static int [] dx = {+1, 0, -1, 0}; // neighbours offsets in the grid
static int [] dy = {0, +1, 0, -1}; // dtto
static boolean [][][] node; // node = street crossing
static int [] queueBlack, queueWhite; // queues for nodes
static boolean [][] used;
static int headBlack, tailBlack, headWhite , tailWhite ;
static int startX, startY, targetX, targetY;
static int currdist, inextdist; // register distances of nodes in the queue
static boolean hasBlackEdge(int y, int x) {
if ((x < N-1) && (!node[y][x][EAST])) return true;
if ((x > 0 ) && (!node[y][x][WEST])) return true;
if ((y < M-1) && (!node[y][x][NORTH])) return true;
if ((y > 0 ) && (!node[y][x][SOUTH])) return true;
return false;
}
static boolean wasUsed (int y, int x) {
if ((x >= N) || (x < 0) || (y >= M ) || (y < 0) || used[y][x] ) return true;
used[y][x] = true;
return false;
}
static boolean searchWhites(int y, int x) {
int neighX, neighY;
tailWhite = headWhite = 0;
queueWhite[headWhite] = y*N+x; // unique node label !!!
while (headWhite <= tailWhite) {
y = queueWhite[headWhite]/N; x = queueWhite[headWhite++]%N;
for(int dir = 0; dir < 4; dir++)
if (node[y][x][dir]) {
neighY = y+dy[dir]; neighX= x + dx[dir];
if (wasUsed(neighY, neighX)) continue;
if ((neighY == targetY) && (neighX == targetX))
{ System.out.printf("%d\n", currdist); return true; } // found
if (hasBlackEdge(neighY, neighX))
queueBlack[++tailBlack] = neighY*N + neighX; // push to black
queueWhite[++tailWhite] = neighY*N + neighX; // push white anaway
}
} // while unempty white q
return false;
}
static void searchBlacks(){
int y, x, neighX, neighY;
while(headBlack<= tailBlack) {
if (headBlack== inextdist) {currdist++; inextdist = tailBlack+1;}
y = queueBlack[headBlack]/N; x = queueBlack[headBlack++]%N;
for(int dir = 0; dir < 4; dir++) {
neighY = y+dy[dir]; neighX = x + dx[dir];
if ( wasUsed(neighY, neighX)) continue;
if ((neighY == targetY) && (neighX == targetX))
{ System.out.printf("%d\n", currdist); return; }
queueBlack[++tailBlack] = neighY*N + neighX; // push this node anyway
if (searchWhites(neighY, neighX)) return; // push all white-adjacent nodes
} // for 4 directions
} // while unempty q
}
// ***************************************************************************
// M A I N
// ***************************************************************************
public static void main(String[] args) throws IOException {
getvals();
used[startX][startY] = true;
currdist = head1 = tail1 = 0;
queueBlack[tail1] = startX*N + startY; //unique node label !!!
if (!searchWhites(startX, startY)) { // if not in the same illuminated region
inextdist = tail1+1; currdist = 1;
searchBlacks();
}
}
// ***************************************************************************
// I / O
// ***************************************************************************
static void getvals() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
t1 = System.currentTimeMillis();
N = Integer.valueOf(st.nextToken());
M = Integer.valueOf(st.nextToken());
L = Integer.valueOf(st.nextToken());
node = new boolean [M][N][4];
used = new boolean[M][N];
queueBlack = new int[M*N];
queueWhite = new int[M*N];
st = new StringTokenizer(br.readLine());
startY = Integer.valueOf(st.nextToken());
startX = Integer.valueOf(st.nextToken());
targetX = Integer.valueOf(st.nextToken());
targetY = Integer.valueOf(st.nextToken());
int x1, x2, y1, y2;
for(int i = 1; i <= L; i++) {
st = new StringTokenizer(br.readLine());
x1 = Integer.valueOf(st.nextToken());
y1 = Integer.valueOf(st.nextToken());
x2 = Integer.valueOf(st.nextToken());
y2 = Integer.valueOf(st.nextToken());
for(int y = y1; y <= y2; y++)
for(int x = x1; x < x2; x++)
node[y][x][EAST] = node[y][x+1][WEST] = true;
for(int y = y1; y < y2; y++)
for(int x = x1; x <= x2; x++)
node[y][x][NORTH] = node[y+1][x][SOUTH] = true;
}
}
}
\\
2. Dijkstrův algoritmus\\
Při použití Dijkstrova algoritmu postupujeme standardně, vybudujeme graf, můžeme použít stejnou reprezentaci grafu, jakou bychom použili v předcházející variantě s procházením do šířky. Osvětlené ulice ohodnotíme například nulou, neosvětlené jedničkou a Dijkstrův algoritmus už za nás sám hledá nejkratší cestu (nebo alespoň její délku, tedy počet černých hran, tedy počet jedniček na cestě) ze startu do cíle. Tuto variantu nelze asi příliš dále komentovat, po ohodnocení uvedeném výše se úloha redukuje na zcela mechanickou základní aplikaci Dijkstrova algoritmu, bez žádných dodatečných nápadů nebo modifikací.\\
Bez úpravy uvádíme níže úspěšné studentské řešení vzniklé během cca 2 hodin během zkoušky. Centrální pro celé řešení je funkce solve().
import java.util.Comparator;
public class SearchNodeComparator implements Comparator{
@Override
public int compare(SearchNode o1, SearchNode o2) {
return o1.price - o2.price;
}
}
// **************************************************************
public class SearchNode {
public final int x;
public final int y;
public final int price;
public SearchNode(int x, int y, int price) {
this.x = x;
this.y = y;
this.price = price;
}
}
// **************************************************************
import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.util.PriorityQueue;
public class Main {
private static InputStream stream;
private static int N;
private static int M;
private static int L;
private static int[][] cross;
private static boolean[][] right;
private static boolean[][] up;
private static int sx, sy, ex, ey; //start and end coordinates
private static PriorityQueue queue;
public static void main(String[] args) throws IOException {
init();
setStream(false);
getInput();
//testInput();
solve();
}
private static void setStream(boolean file) throws FileNotFoundException {
if (file) {
File publicData = new File("datapub/pub01.in");
if (!publicData.exists()) {
System.out.println("CHYBA public data neexistuji");
System.exit(1);
}
stream = new BufferedInputStream(new FileInputStream(publicData));
} else {
stream = System.in;
}
}
private static int readInt() throws IOException {
int sum = 0;
int scan = stream.read();
while (scan < 48 || scan > 57) {
scan = stream.read();
}
while (scan >= 48 && scan <= 57) {
sum *= 10;
sum += scan - 48;
scan = stream.read();
}
return sum;
}
private static void getInput() throws IOException {
N = readInt();
M = readInt();
L = readInt();
sx = readInt();
sy = readInt();
ex = readInt();
ey = readInt();
cross = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cross[i][j] = Integer.MAX_VALUE;
}
}
right = new boolean[N][M];
up = new boolean[N][M];
for (int i = 0; i < L; i++) {
int a, b, c, d;
a = readInt();
b = readInt();
c = readInt();
d = readInt();
lightStreets(a, b, c, d);
}
}
private static void testInput() {
System.out.println("N " + N + " M " + M + " L " + L);
for (int y = M-1; y >=0; y--) {
for (int x = 0; x < N; x++) {
System.out.print(up[x][y]?"X ":"O ");
}
System.out.println("");
}
System.out.println("");
for (int y = M-1; y >=0; y--) {
for (int x = 0; x < N; x++) {
System.out.print(right[x][y]?"X ":"O ");
}
System.out.println("");
}
}
private static void solve() {
cross[sx][sy] = 0;
SearchNode node = new SearchNode(sx, sy, 0);
while (node.x != ex || node.y != ey) {
expand(node);
node = queue.poll();
}
System.out.println(node.price);
}
private static void init() {
queue = new PriorityQueue<>(1024, new SearchNodeComparator());
}
private static void expand(SearchNode node) {
int x = node.x; //x sloupec
int y = node.y; //y je radek
int p = node.price;
if (up[x][y]) {
if (y < M-1 && p < cross[x][y + 1]) {
cross[x][y + 1] = p;
queue.add(new SearchNode(x, y + 1, p));
}
} else {
if (y < M-1 && (p + 1) < cross[x][y + 1]) {
cross[x][y + 1] = p + 1;
queue.add(new SearchNode(x, y + 1, p + 1));
}
}
if (y > 0) {
if (up[x][y - 1]) {
if (p < cross[x][y - 1]) {
cross[x][y - 1] = p;
queue.add(new SearchNode(x, y - 1, p));
}
} else {
if ((p + 1) < cross[x][y - 1]) {
cross[x][y - 1] = p + 1;
queue.add(new SearchNode(x, y - 1, p + 1));
}
}
}
if (right[x][y]) {
if (x < N-1 && p < cross[x + 1][y]) {
cross[x + 1][y] = p;
queue.add(new SearchNode(x + 1, y, p));
}
} else {
if (x < N-1 && (p + 1) < cross[x + 1][y]) {
cross[x + 1][y] = p + 1;
queue.add(new SearchNode(x + 1, y, p + 1));
}
}
if (x > 0) {
if (right[x - 1][y]) {
if (p < cross[x - 1][y]) {
cross[x - 1][y] = p;
queue.add(new SearchNode(x - 1, y, p));
}
} else {
if ((p + 1) < cross[x - 1][y]) {
cross[x - 1][y] = p + 1;
queue.add(new SearchNode(x - 1, y, p + 1));
}
}
}
}
private static void lightStreets(int a, int b, int c, int d) {
for (int x = a; x <= c; x++) {
for (int y = b; y < d; y++) {
up[x][y] = true;
}
}
for (int x = a; x < c; x++) {
for (int y = b; y <= d; y++) {
right[x][y] = true;
}
}
}
}