Tävlingsprogrammering/Uppgifter/Skolvägen

Skolvägen

Cissi går från sitt hem till skolan längs en lång gata som går i väst-östlig riktning. På sin väg passerar hon ett antal korsningar där tvärgator utgår norrut (N), söderut (S) eller både norrut och söderut (B). Vid varje korsning finns övergångsställen på både tvärgator och huvudgata (se figuren ovan), och dessa måste givetvis följas.

Den streckade linjen visar Cissis väg i första exemplet.

Både hemmet och skolan ligger på norra sidan av gatan. Skriv ett program som hjälper Cissi att beräkna det minsta antalet gator hon måste korsa på sin väg till skolan.

Indata

En rad med högst 1000 bokstäver, som vardera är N, S eller B. Bokstäverna beskriver korsningarna i precis den ordning som Cissi passerar dem.

Delpoäng: För 40% av poängen är antalet bokstäver högst 20.

Utdata

En rad med ett heltal, det minsta antalet gator Cissi behöver korsa.

Två exempel

SBSNNB

ska ge svaret

4

SBSNNBSNNSSSNNNB

ska ge svaret

8

Lösning

Detta är ett enkelt exempel på dynamisk programmering. När Cissi har kommit en bit på vägen är det enda hon behöver veta för att lösa resten av problemet hur många korsningar hon behövt passera om hon är på norra sidan (n) och hur många korsningar hon behövt passera om hon är på södra sidan (s). Det är alltså ointressant exakt vilken väg hon har tagit för att komma dit.

Lösning i C:

#include <stdio.h>
#include <string.h>

int MIN(int p,int q) {return p<q?p:q;} 

int main() {
  char kors[1001];
  int N,n,s,ss,i;
  scanf("%s", kors);
  N=strlen(kors);
  n=0;    //Antal vägar hittills korsade om man är på norra sidan 
  s=1;    //Antal vägar hittills korsade om man är på södra sidan
  for(i=0;i<N;i++) {   //Loopa över korsningarna
    switch(kors[i]) {     //Korsa tvärgatorna
      case 'N': n++; break;
      case 'S': s++; break;
      case 'B': n++; s++; break;
    } 
    ss=s;            //Temporär varibel som inte skrivs över
    s=MIN(ss,n+1);   //Testa att korsa huvudgatan (norr till söder)
    n=MIN(n,ss+1);   //Testa att korsa huvudgatan (söder till norr)
  }
  printf("%d\n",n);  //Skolan ligger på norra sidan
  return 0;
}