Tävlingsprogrammering/Uppgifter/Kanoner
Kanoner
Vi är under attack av en fientlig styrka och måste rikta in kanonerna i våra torn mot de angripande marktrupperna. Terrängen kan representeras med ett rektangulärt rutnät på RxK rutor.
Varje torn är utrustat med två kanoner som sitter fast i 90 graders vinkel i förhållande till varandra. Kammaren i tornet där kanonerna står har fyra fönster som vetter norr, öster, söder respektive väster. På grund av kanonernas konstruktion kan de endast riktas så att de skjuter enligt någon av följande konfigurationer:
1. En kanon skjuter västerut och den andra söderut. 2. En kanon skjuter söderut och den andra österut. 3. En kanon skjuter österut och den andra norrut. 4. En kanon skjuter norrut och den andra västerut.
En kanonkula som träffar en angripare dödar honom och fortsätter vidare i samma riktning. Om kanonkulan träffar något av våra slott stannar kulan och orsakar ingen mer skada (slotten är stora och starka). Men om en kanonkula träffar ett försvarstorn förstörs det.
Vi vill nu rikta in kanonerna så att, när vi skjuter exakt ett skott från varje kanon i varje torn, alla angripare dör och inget torn tar skada.
Indata
Den första raden innehåller två heltal R och K (1 ≤ R, K ≤ 100), storleken på kartan.
De följande R raderna innehåller K tecken vardera, där 'T' motsvarar ett torn, 'a' en angripare, '#' ett slott och '.' en tom yta.
Du kan utgå ifrån att det alltid finns en lösning, om än inte unik.
Utdata
Skriv ut kartan från indata i samma format, men ersätt tornen med riktningen på kanonerna enligt listan ovan. Dvs, varje 'T' ska ha ersatts med någon av siffrorna '1', '2', '3' eller '4'. Om det finns flera lösningar kan du ange vilken som helst av dem.
Bedömning
I 10% av testfallen kommer det finnas mindre än 10 kanoner.
Exempel 1: Indata
9 13 ............. ...........a. .a.T..aaaa#.. ............. .T#a..a....T. ............. .a.T..T....a. ............. ......a......
Exempel 1: Utdata
............. ...........a. .a.3..aaaa#.. ............. .4#a..a....4. ............. .a.1..2....a. ............. ......a......
Exempel 2: Indata
5 9 .a..T..a. .T..a.... .a..#..a. ....a..T. .a..T..a.
Exempel 2: Utdata
.a..1..a. .1..a.... .a..#..a. ....a..4. .a..2..a.
Exempel 3: Indata
9 8 a.Taaaaa aaaaaaTa aTaaaaaa aaaaTaaa Taaaaaaa ..#aaTaa aaaaaaaT aaaTa.a. .aTaaaaa
Exempel 3: Utdata
a.2aaaaa aaaaaa1a a2aaaaaa aaaa2aaa 3aaaaaaa ..#aa3aa aaaaaaa4 aaa4a.a. .a2aaaaa
Exempel 4: Indata
3 3 T.T ... T.T
Exempel 4: Utdata
4.3 ... 1.2
Lösning
[redigera]Varje torn skjuter i exakt en av riktningarna norr/söder och i exakt en av riktningarna öster/väster. Vi kan beteckna det med två boolska variabler per torn. För torn i:
- Om tornet skjuter väster, så är variabeln Li true
- Om tornet skjuter norr, så är variabeln Ui true
- Om tornet skjuter öster, så är variabeln Li false, och således ¬Li ("icke Li") är true
- Om tornet skjuter söder, så är variabeln Ui false, och således ¬Ui ("icke Ui") är true
Uppgiften blir nu att bestämma värdena för L och U för varje torn. Vissa av värdena kan sättas på en gång. Om två torn befinner sig på samma rad, och det inte finns något slott mellan dem, så kan de vänstra tornet inte skjuter öster och det högre tornet inte skjuta väster (tornen får inte förstöra varandra).
Varje attackerare bidrar med ytterligare begränsningar då var och en måste träffas av minst ett torn. För varje attackerare kollar vi alla fyra riktningar efter vilka torn som är kandidater att slå ut attackeraren. En viktig detalj är att det faktiskt bara kan finnas två kandidater för varje attackerare. Om ett torn befinner sig norr och ett annat befinner sig söder om samma attackerar kan inget av dem skjuta åt det hållet, för då skulle ett av tornen förstöras. Varje attackerare kan alltså bara angripas av högst ett torn i norr-sydlig riktning, och av högst ett annat torn i väst-östlig riktning.
Om det bara finns ett torn som kan slå ut en attackera så är det lätt, då kan vi direkt sätta en av variablerna Li eller Ui. I annat fall får vi ett logiskt uttryck på följande form: LA ∨ ¬UB ("jag måste antingen träffas av torn A som skjuter väster eller torn B som skjuter söder"). Vi kommer få ett antal logiska uttryck (klausuler) på denna form, och alla måste vara sanna. Denna typ av problem är kända som satisfierbarhetsproblem (SAT) och är generellt sätt svåra att lösa. Här har vi dock ett specialfall då varje klausul i uttrycket består av högst 2 literaler. Detta problem är känt som 2-SAT och går att lösa effektivt. Lätt förenklat kan man säga att man bara antar att en variabel har ett visst värde (true eller false) och sedan ser om detta leder till en motsägelse. Om inte, så går man vidare till nästa variabel osv. Läs mer om 2-SAT på vår träningssite, http://www.csc.kth.se/contest/ioi/ioitraning/grafsat.htm
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
char map[102][102];
int torn[102][102];
int antal_torn = 0;
//Index: 0: skjuta höger? 1: skjuta vänster? 2: skjuta ner? 3: skjuta upp?
int torn_res[10000][4]; //Värden: 0 = inget värde än, 1 = sant, 2 = falskt
struct Nod {
vector<int> in;
vector<int> ut;
} graph[40000];
//Varje torn kommmer att ha fyra noder, två för höger-vänster, två för ner-upp
//Noden hittas med torn_id*4+riktning (enligt ovan)
#define NEG(i) ((i)^1)
bool vis[40000];
int stack[40000];
int sp = 0;
struct Comp {
vector<int> noder;
bool visited; //Om man har satt den till sant genom att man följer en kedja
int status; //0: ej klart, 1: sant, 2: falskt
} comp[40000];
int comp_id[40000];
int ncomp = 0;
static void DFS1(int v){
vis[v] = true;
Nod& n = graph[v];
for(vector<int>::iterator it = n.ut.begin(); it != n.ut.end(); ++it){
if (!vis[*it])
DFS1(*it);
}
stack[sp++] = v;
}
static void DFS2(int v){
vis[v] = true;
comp_id[v] = ncomp;
comp[ncomp].noder.push_back(v);
int tmp;
if ((tmp = torn_res[v/4][v%4])) comp[ncomp].status = tmp;
Nod& n = graph[v];
for(vector<int>::iterator it = n.in.begin(); it != n.in.end(); ++it){
if (!vis[*it])
DFS2(*it);
}
}
static void set_true(int i){
Comp& c = comp[i];
if (c.visited) return;
c.visited = true;
c.status = 1;
for(vector<int>::iterator it = c.noder.begin(); it != c.noder.end(); ++it){
//Fyll i svaret
torn_res[(*it)/4][(*it)%4] = 1;
Nod& n = graph[*it];
for(vector<int>::iterator ut = n.ut.begin(); ut != n.ut.end(); ++ut){
set_true(comp_id[*ut]);
}
}
}
static void two_sat(){
//Bygg SCC med automatisk topologisk sortering
for(int i=0; i<antal_torn*4; i++) if (!vis[i]) DFS1(i);
memset(vis, 0, antal_torn*4*sizeof(bool));
while(sp--) if (!vis[stack[sp]]){
DFS2(stack[sp]);
ncomp++;
}
//comp är en topologiskt sorterad array, comp_id[nod_id] hittar comp-indexet för en viss nod
for(int i=0; i<ncomp; i++){
Comp& c = comp[i];
if (c.status == 0){
//Om den inte är sann från början kan vi sätta den till falskt
c.status = 2;
//Men då måste vi sätta motsatsen till sann. Det går bra att vänta med att sätta implikationerna tills vi besöker den, eftersom vi ändå kommer att besöka denna före det den implicerar (eftersom vi har allt topologiskt ordnat).
comp[comp_id[NEG(c.noder.front())]].status = 1;
} else if (c.status == 1){
//Om den redan är sann måste vi se till att alla implikationer också är sanna
set_true(i);
}
if (c.status == 2) for(vector<int>::iterator it = c.noder.begin(); it != c.noder.end(); ++it){
//Fyll i svaret
torn_res[(*it)/4][(*it)%4] = 2;
}
}
}
int main(){
int R, K;
scanf("%d %d", &R, &K);
//Sätt en ram med # runt för enkelhetens skull
for(int i=1; i<=R; i++){
scanf("%s", &map[i][1]);
map[i][0] = map[i][K+1] = '#';
}
for(int i=0; i<K+2; i++){
map[0][i] = map[R+1][i] = '#';
}
//Sätt ett index på varje torn
for(int i=1; i<=R; i++) for(int j=1; j<=K; j++)
if (map[i][j] == 'T')
torn[i][j] = antal_torn++;
static const int D[4][2] = {{0,-1}, {0,1}, {-1,0}, {1,0}};
//Gör så att tornen inte kan skjuta på sig själva
for(int i=1; i<=R; i++) for(int j=1; j<=K; j++)
if (map[i][j] == 'T'){
int t1 = torn[i][j];
for(int k=0; k<4; k++){
int y=i, x=j;
char res;
while(res = map[y+=D[k][0]][x+=D[k][1]], res == '.' || res == 'a');
if (res == 'T'){
int t2 = torn[y][x];
torn_res[t1][k] = torn_res[t2][NEG(k)] = 1;
torn_res[t1][NEG(k)] = torn_res[t2][k] = 2;
}
}
}
for(int i=1; i<=R; i++) for(int j=1; j<=K; j++){
if (map[i][j] == 'a'){
int tornen[4] = {-1, -1, -1, -1};
for(int k=0; k<4; k++){
int y=i, x=j;
char res;
while(res = map[y+=D[k][0]][x+=D[k][1]], res == '.' || res == 'a');
if (res == 'T')
tornen[k] = torn[y][x];
}
//Om det finns 0 eller 2 torn i horisontell riktning
if ((tornen[0] != -1 ^ tornen[1] != -1) == 0){
//Då måste den träffas av antingen ett torn upp eller ner
if (tornen[2] != -1){
torn_res[tornen[2]][2] = 1;
torn_res[tornen[2]][3] = 2;
} else {
torn_res[tornen[3]][2] = 2;
torn_res[tornen[3]][3] = 1;
}
//Om det finns 0 eller 2 torn i vertikal riktning
} else if ((tornen[2] != -1 ^ tornen[3] != -1) == 0){
//Då måste den träffas av antingen ett torn vänster eller höger
if (tornen[0] != -1){
torn_res[tornen[0]][0] = 1;
torn_res[tornen[0]][1] = 2;
} else {
torn_res[tornen[1]][0] = 2;
torn_res[tornen[1]][1] = 1;
}
} else {
//Två möjligheter, antingen i vertikal riktning eller horisontell
int hor, ver;
if (tornen[0] != -1)
hor = tornen[0]*4+0;
else hor = tornen[1]*4+1;
if (tornen[2] != -1)
ver = tornen[2]*4+2;
else ver = tornen[3]*4+3;
graph[NEG(hor)].ut.push_back(ver);
graph[ver].in.push_back(NEG(hor));
graph[NEG(ver)].ut.push_back(hor);
graph[hor].in.push_back(NEG(ver));
}
}
}
two_sat();
int t = 0;
for(int i=1; i<=R; i++){
for(int j=1; j<=K; j++)
if (map[i][j] == 'T'){
int* res = torn_res[t];
if (res[1]==1 && res[2]==1) map[i][j] = '1';
else if (res[0]==1 && res[2]==1) map[i][j] = '2';
else if (res[0]==1 && res[3]==1) map[i][j] = '3';
else if (res[1]==1 && res[3]==1) map[i][j] = '4';
t++;
}
fwrite(map[i]+1, 1, K, stdout);
putchar('\n');
}
}