TCO 2011 Qualifier 2 500P
2011年5月19日晚7点，参加了【TCO 2011 Qualification Round 2】

250P：很简单的题，但题目提供了个看似有用实则无用的条件，把我给忽悠了，以为有点复杂呢，居然34分钟，叹叹。
500P：一直在想怎么回溯，就没想下BFS，不过就算想到了，也应该搞不定，不知怎么判重。

500P Problem
一个一维的地图，每个点可以是'.'、'K'和'C'，'.'表示空，'K'表示经过该点时其步长不可为K的倍数，'C'表示经过该点时其步长必须为C的倍数，起点和终点分别在两端(必为'.')，在任意时刻，可以选择向前、向后和不走这三种方式进行移动，求从起点到终点的最小步长。

500P Solution
如果不加判重会超时，而下面这两种判重都能AC，但我还不是很清楚。

public class KindAndCruel {public int crossTheField(String str, int K, int C) {LinkedList<State> q = new LinkedList<State>();//int M = K*C;//boolean[][] visited = new boolean[str.length()][M];boolean[][][] visited = new boolean[str.length()][K][C];q.add(new State(0, 0));while(q.size() > 0) {State s = q.removeFirst();/*if(visited[s.pos][s.steps%M])continue;visited[s.pos][s.steps%M] = true;*/if(visited[s.pos][s.steps%K][s.steps%C])continue;visited[s.pos][s.steps%K][s.steps%C] = true;if(s.pos == str.length()-1)return s.steps;char ch = str.charAt(s.pos);if(ch == 'K' && s.steps%K == 0)continue;if(ch == 'C' && s.steps%C != 0)continue;q.add(new State(s.pos+1, s.steps+1));q.add(new State(s.pos, s.steps+1));if(s.pos > 0)q.add(new State(s.pos-1, s.steps+1));}return -1;}class State {int pos;int steps;State(int pos, int steps) {this.pos = pos;this.steps = steps;}}}