UVa 10818

From Algorithmist
Jump to: navigation, search

10818 - Dora Trip[edit]

Summary[edit]

Variant of Traveling Salesperson Problem.

Explanation[edit]

This problem is NP-complete. But since the number of places that Nobita has to visit is no more than 10, a simple search suffices. Note that we ask for the lexicographically smallest shortest path.

Gotcha's[edit]

Especially for C/C++ users: be careful of how your program reads the input.

Input[edit]

7 7 
####### 
#*   *# 
#  X X# 
#  S *# 
#*   *# 
#*****# 
####### 
6 6 
###### 
#*  *# 
#X  X# 
#   *# 
#S  *# 
###### 
6 6 
###### 
#S  *# 
#  XX# 
#   *# 
#*  *# 
###### 
5 5 
##### 
#S X# 
# *X# 
#*#*# 
#####
0 0

Output[edit]

EESSWWWWNNNNEEEEWSSW 
EEENWNNEWWWESSSW 
EEEWWSSEESWWWNNN 
ESWSNN