PKU 1452 - Signal Box

Autor da análise: tsebayothtsebayoth

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1452

Resumo

O problema descreve um grafo (composto por 2 tipos diferentes de vértices, switches e signals) e algumas regras (as regras expressão a direção que você deve tomar no caminho entre 2 vértices). Dados 2 vértices origem e destino, você precisa devolver um caminho entre eles que satisfaça as regras.

Solução

O problema é simples, apenas o enunciado é confuso. O mais indicado é fazer um grafo implícito, observando a construção descrita no enunciado. A partir desse grafo, você roda um $DFS(origem, destino)$, sem se importar com as regras. Se você não encontrar um caminho, a resposta é "NOT POSSIBLE", caso contrário você precisa adequar o caminho encontrado, digamos $P=v_1,v_2,v_3,...,v_k$, às regras impostas. Para isso, para cada par $v_i,v_j \in P$, com $i<j$, ao qual existe uma regra "$v_i$ $v_j$ $s$" ($s \in \{+,-\}$), você roda $DFS(v_i,v_j,s)$, ou seja, procura um caminho de $v_i$ até $v_j$ tomando a direção "s", se tal caminho existe, você substitui o intervalo $v_i,v_{i+1},...v_j$ em P por esse novo caminho que você encontrou. Pronto, ao final você terá uma solução válida para o problema.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License