Tävlingsprogrammering/Uppgifter/Kinesiska Muren
Kinesiska Muren
Den kinesiska kejsaren måste försvara sitt land från de angripande mongolerna. Givet en förenklad karta över det aktuella området (ett M × N rutnät), där vissa rutor är hinder (markerade med ’#’), bestäm det minsta antal rutor där en mur måste byggas som gör det omöjligt att ta sig från den övre raden i rutnätet (mongolernas område) till den nedersta raden i rutnätet (kinesiskt område). De mongoliska marktrupperna kan bara förflytta sig från en ruta till någon av sina fyra grannrutor om ingen av dessa är hinder eller mur.
Indata
Första raden i filen muren.dat innehåller två heltal, M och N (3 ≤ M,N ≤ 1000), storleken på rutnätet. Därefter följer N rader, var och en innehållande M tecken. Varje tecken är antingen ’.’ eller ’#’. Den första och sista raden innehåller enbart ’.’ .
Utdata
Programmet ska först skriva ut en rad med ett tal, det minimala antalet rutor där det måste byggas en mur. Därefter ska det skriva N rader som visar på vilka rutor muren har byggts. Använd samma format som i indatat, men bokstaven ’M’ på de rutor där mur har byggts. Det är tillåtet att bygga mur även på första och sista raden.
Exempel 1
5 4 ..... ..#.. .#..# .....
Svar
2 ..... ..#.. M#.M# .....
Exempel 2
12 9 ............ ....#....... ........#... .##..#...... .....#...... ....##..#... ............ .#....#....# ............
Svar
6 ............ ....#....... ........#... M##..#...... ...M.#...... ....##MM#M.. ..........M. .#....#....# ............
Lösning
[redigera]Rätt så snabbt inser man att problemet går ut på att hitta den kortaste vägen från den vänstra sidan till den högra sidan (eller tvärtom) där kostnaden för att gå på en ruta med '.' är 1 och 0 för '#'. Observera att det är helt OK att gå diagonalt också (eftersom vi egentligen bygger muren).
Till en början kan man lura sig att tro att det bara är att gå från vänster till höger och addera 1 eller 0 till den minsta summan av (x-1,y-1), (x-1,y) och (x-1,y+1) för att få fram minsta antalet drag för att nå (x,y), men så är inte fallet, eftersom hindren kan bilda mönster som minst sagt slingrar sig fram och tillbaka.
Däremot fungerar Dijkstras Algoritm alldeles utmärkt för att lösa problemet. Programmerar man den i Java måste man dock tänka på att man inte allokerar minnesutrymme för ett objekt, lägger det på heapen och sedan plockar upp det bara för att konstatera att rutan redan besökts och slänga objektet. Visst är det det smidigaste sättet att programmera på, men faktum är att själva minnesallokeringen för nya objekt (states) kommer då att vara vår mest frekventa och dyraste operation, vilket får programmet att ta ca 15 sek för testfall 5. Lösningen är att kolla om man redan besökt en ruta innan man skapar ett nytt objekt och därtill också markerar en ruta som besökt i samma tillfälle som man lägger den på heapen (vilket rent generellt inte alltid är korrekt att göra, men just i det här problemet går det bra).
Lösning i Java.
import java.util.*;
import java.io.*;
public class KinesiskaMuren
{
//Landskapet.
static char [][] grid;
//Håller reda på om vi besökt [y][x].
static boolean [][] map;
//Vår kö (heap).
static PriorityQueue <State> qu = new PriorityQueue <State> ();
//Metod för att låta ruta (x,y) ingå i muren.
public static void add(int x, int y, int mur, State s)
{
//Om rutan redan har blivit besökt, så var det av en kortare (eller lika kort) mur.
if(map[y][x]) return;
//Markerar som besökt.
map[y][x] = true;
//Lägger det här tillståndet på heapen.
qu.add(new State(x,y,mur,s));
}
//Orka fånga exceptions. Vi är lata och säkra på vår sak.
public static void main(String [] klein) throws FileNotFoundException
{
//long tid = System.currentTimeMillis();
//Vi ska läsa av filen muren.dat.
Scanner scan = new Scanner(new File("muren.dat"));
final int M = scan.nextInt();
final int N = scan.nextInt();
map = new boolean [N][M];
//Läser in planen.
grid = new char [N][];
for(int i = 0; i<N; i++) grid[i] = scan.next().toCharArray();
//Vi börjar att bygga vid vänsterkanten.
//Lägger alla rutor längst till vänster på heapen.
for(int i = 0; i<N; i++) add(0,i,0,null);
State s;
while(true)
{
//Plockar ut den med minst murbitar (drag).
s = qu.poll();
//Vi är framme och har byggt muren.
if(s.x==M-1) break;
//Går i alla riktningar.
add(s.x+1, s.y, s.mur, s);
if(s.y<N-1)
{
add(s.x+1, s.y+1, s.mur, s);
add(s.x, s.y+1, s.mur, s);
if(s.x>0) add(s.x-1, s.y+1, s.mur, s);
}
if(s.x>0)
{
add(s.x-1, s.y, s.mur, s);
if(s.y>0) add(s.x-1, s.y-1, s.mur, s);
}
if(s.y>0)
{
add(s.x, s.y-1, s.mur, s);
add(s.x+1, s.y-1, s.mur, s);
}
}
//Antalet murbitar.
int svar = s.mur;
//Tar nu reda på hur muren ska se ut (och "bygger" den).
while(s!=null)
{
if(grid[s.y][s.x]=='.') grid[s.y][s.x] = 'M';
s = s.prev;
}
//Skriver antalet rutor..
System.out.println(svar);
//System.out.println("Tid: " + (System.currentTimeMillis()-tid));
//Skriver ut muren.
for(int i = 0; i<N; i++) System.out.println(grid[i]);
}
private static class State implements Comparable<State>
{
//Koordinater och antalet drag (murbitar) för att nå positionen.
int x, y, mur;
//Rutan (koordinaten) vi kom ifrån. (Den tidigare biten i muren.)
State prev;
//Konstruktor.
State(int x, int y, int mur, State s)
{
//Ska muren gå här måste en murbit läggas till.
if(grid[y][x]=='.') mur++;
this.x = x; this.y = y;
this.mur = mur; prev = s;
}
//Så att objekt av klassen kan läggas på heapen (kön).
//Den med minst murbitar ska hamna högst upp.
public int compareTo(State s)
{
if(mur<s.mur) return -1;
else return 1;
}
}
}
Liknande lösning i C++. Lägg märke till att eftersom vägarnas längder bara kan vara 0 eller 1 går det bra att använda en vanlig deque, istället för en prioritetskö. De vägar som är 0 i längd lägger man till kön med push_front, och de vägar som är 1 i längd lägger man till med push_back.
#include <cstdio>
#include <deque>
#include <utility>
#define INF (1<<20)
using namespace std;
int N, M;
char karta[1000][1004];
pair<int, int> parent[1000][1001];
#define START make_pair(-1, -1)
int dist[1000][1000];
int main(){
scanf("%d%d", &M, &N);
for(int i=0; i<N; i++){
scanf("%s", karta[i]);
for(int j=1; j<M; j++)
dist[i][j] = INF;
}
for(int i=0; i<N; i++)
parent[i][0] = START;
deque<pair<int, pair<int, int> > > q; //Steg, y, x
for(int i=0; i<N; i++){
if (karta[i][0] == '.'){
q.push_back(make_pair(1, make_pair(i, 0)));
dist[i][0] = 1;
} else {
q.push_front(make_pair(0, make_pair(i, 0)));
dist[i][1] = 0;
}
}
while(!q.empty()){
pair<int, pair<int, int> > elem = q.front(); q.pop_front();
int steg = elem.first;
int y = elem.second.first;
int x = elem.second.second;
if (steg != dist[y][x])
continue;
if (x == M-1){
printf("%d\n", steg);
pair<int, int> ruta = elem.second;
for(; ruta != START; ruta = parent[ruta.first][ruta.second]){
if (karta[ruta.first][ruta.second] == '.')
karta[ruta.first][ruta.second] = 'M';
}
for(int i=0; i<N; i++){
fwrite(karta[i], 1, M, stdout);
putchar('\n');
}
break;
}
static const int koord[8][2] = {{0, 1}, {-1, 1}, {1, 1}, {-1, 0}, {1, 0}, {-1, -1}, {1, -1}, {0, -1}};
for(int i=0; i<8; i++){
int ny = y+koord[i][0];
int nx = x+koord[i][1];
if (ny >= 0 && ny < N && nx > 0 && nx < M){
int nsteg = steg+(karta[ny][nx] == '.');
if (nsteg < dist[ny][nx]){
dist[ny][nx] = nsteg;
parent[ny][nx] = elem.second;
if (karta[ny][nx] == '.')
q.push_back(make_pair(nsteg, make_pair(ny, nx)));
else
q.push_front(make_pair(nsteg, make_pair(ny, nx)));
}
}
}
}
}