/* Quick Search, MCPC 2010 Problem G by Andy Harrington
input:
Each dataset:
s n p <paths> Number of sites, searchers, number of connecting paths
Each path token is a pair of capital letters.
Algorithm: The input data gives a *site* graph.
A breadth first search is done over a related *state* graph. In the
state graph a node is a pair of integers encoding the sorted current
sites of searches and set of sites already visited as a bit field:
The variable length location array is encoded as a single integer, base s.
Add site i to those visited: visted |= 1 << i
A state graph edge involves each searcher moving along a path of
the site graph - a possible single time step.
Because of the variable number of searchers, the full collection
of neighbors in the state graph is found recursively.
A boolean array stored which states have been found. What states needs to be
traversed (at current distance, at next distance) are stored in Lists.
The breadth-first search terminates when a state is reached with all
sites visited.
*/
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
public class search // version with big encoded boolean array: found
{
public static int s, n, p, // # nodes, searchers, edges
allVisited, // visited bitfield in terminal node
MIN_S = 2, MAX_S = 10, MAX_N = 4, MAX_P = 20; //match final problem!
static boolean[][] edge; // in original graph
static boolean[][]found; //found[vCode][locCode] true when find state
static int locCode(int[] loc) {
int[] lc = loc.clone();
Arrays.sort(lc);
int sum = 0;
for (int i = n-1; i >= 0; i--)
sum = s*sum + lc[i];
return sum;
}
static int[] locCodeToLoc(int lCode) {
int[] loc = new int[n];
for (int i = 0; i < n; i++) {
loc[i] = lCode % s;
lCode /= s;
}
return loc;
}
public static void main(String[] args) throws Exception {
String file = (args.length > 0) ? args[0] : "search.in";
Scanner in = new Scanner(new File(file));
while (true) {
s = in.nextInt();
if (s == 0) break;
n = in.nextInt();
p = in.nextInt();
judgeParamCheck(); // just for judges
edge = new boolean[s][s];
for (int i = 0; i < p; i++) {
String e = in.next();
int from = e.charAt(0) - 'A', to = e.charAt(1) - 'A';
judgeEdgeCheck(from, to); // just for judges
edge[to][from] = edge[from][to] = true;
}
System.out.println(calc());
}
}
//breadth first search through states
//returns number of step to first visiting all sites
static int calc() {
allVisited = (1 << s) - 1;
found = new boolean[allVisited+1][(int)pow(s,n)];
List<int[]> curDist = new ArrayList<int[]>(),//traverse current dist
nextDist; //record neighbors at next distance
curDist.add(new int[]{1,0}); //all at node 0, only node 0 visited
found[1][0] = true;
int steps = 0;
while(true) {
nextDist = new ArrayList<int[]>();
steps += 1;
for (int[] st : curDist)
if (doNeighbors(0, locCodeToLoc(st[1]), st[0], nextDist))
return steps;
curDist = nextDist;
}
}
// nextSearcher 0 .. n-1 recursively find neighbor for nextSearcher,
// nextSearcher = n; all searcher set:
// return true if find terminal state
// or add to next search distance
static boolean doNeighbors(int nextSearcher, int[] at, int visited,
List<int[]> nextDist) {
if (nextSearcher == n) {
for (int i : at)
visited |= 1 << i;
if (visited == allVisited)
return true;
int lCode = locCode(at);
if (!found[visited][lCode]) {
nextDist.add(new int[]{visited, lCode});
found[visited][lCode] = true;
}
return false;
}
int from = at[nextSearcher];
for (int to = 0; to < s; to++)
if (edge[from][to]) {
at[nextSearcher] = to;
if (doNeighbors(nextSearcher+1, at, visited, nextDist))
return true;
}
at[nextSearcher] = from; // now at[nextSearcher] in the original call
return false;
}
// The rest is judge's checks.
static void judgeParamCheck() {
if (MIN_S > s || MAX_S < s || MAX_N < n || MAX_P < p)
System.out.format("param out of range!");
}
static void judgeEdgeCheck(int from, int to) {
if (from >= to) System.out.println("Wrong order!");
if (edge[to][from]) System.out.println("Repeated edge!");
}
}
|