PAT L3-015 ---- 球队“食物链”(DFS)

球队“食物链”
某国的足球联赛中有N支参赛球队，编号从1至N。联赛采用主客场双循环赛制，参赛球队两两之间在双方主场各赛一场。
联赛战罢，结果已经尘埃落定。此时，联赛主席突发奇想，希望从中找出一条包含所有球队的“食物链”，来说明联赛的精彩程度。“食物链”为一个1至N的排列{ T1，T2， …，TN }，满足：球队T1战胜过球队T2，球队T2战胜过球队T3，……，球队T(N-1)战胜过球队TN，球队TN战胜过球队T1。
现在主席请你从联赛结果中找出“食物链”。若存在多条“食物链”，请找出字典序最小的。
注：排列{ a1，a2，…，aN }在字典序上小于排列{ b1，b2， … ，bN }，当且仅当存在整数K（1 <= K <= N），满足：aK < bK且对于任意小于K的正整数i，ai=bi。

输入格式：
输入第一行给出一个整数N（2 <= N <= 20），为参赛球队数。随后N行，每行N个字符，给出了NxN的联赛结果表，其中第i行第j列的字符为球队i在主场对阵球队j的比赛结果：“W”表示球队i战胜球队j，“L”表示球队i负于球队j，“D”表示两队打平，“-”表示无效（当i=j时）。输入中无多余空格。

输出格式：
按题目要求找到“食物链”T1，T2 ，…，TN，将这N个数依次输出在一行上，数字间以1个空格分隔，行的首尾不得有多余空格。若不存在“食物链”，输出“No Solution”。

输入样例1：

5 -LWDW W-LDW WW-LW DWW-W DDLW-

输出样例1：

1 3 5 4 2

输入样例2：

5 -WDDW D-DWL DD-DW DDW-D DDDD-

输出样例2：

No Solution

学校去年举办的程序设计大赛，当时大一只做出来几个水题，后面的大题根本看不懂，时隔将近一年想回去试试能不能AC了那些题。。。。。。事实证明，还有些差距。下面将给出我的思路。

无题解纯自己思考，看完题目想到了TSP问题，算法还算是给了我一定的思绪，我记得好像可与用dfs()解决。
但是做的过程中发现，输入的数据会发生一些问题，仔细排查后原来是由于nexLine()会读取上一个回车导致的，之前也遇到过，只是当时搞明白之后就没有再碰。
接下来就是自己手写dfs()，第一次尝试自己写，而看着模板，但是发现好几个点过不去，比如如何确定跳出时机，如何实现字典序输出，我在主函数写f(1)这不是只能是1开头了。很迷。下面的代码运行不出结果。

import java.util.Scanner;public class Main {static String[][] str;static int n;static int cnt = 0;static boolean[][] vis;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();str = new String[n + 1][n + 1];vis = new boolean[n + 1][n + 1];/*** 注意nextLine()会读取上一个回车* */ for (int i = 0; i < n+1; i++) {String s = in.nextLine();str[i] = s.split("");}f(1); // for (int i = 1; i < n+1; i++) { // for (int j = 1; j < n+1; j++) { // System.out.print(str[i][j] + " "); // } // System.out.println(); // }}private static void f(int m) {// TODO Auto-generated method stubif (cnt > m) {}for (int i = 1; i < n+1; i++) {for (int j = 1; j < n+1; j++) {if (str[i][j].equals("W")) {vis[i][j] = true;f(j);}}}} }

接下来看题解，一开始就发现自己做了一个非常繁琐的操作进行存储数据，而题解的做法是直接用boolean数组存，‘W’是true，‘L’是false，巧妙不少。结尾输出的方式也是巧妙，第一个不打印空格，之后都在打印之前加一个空格，可以巧妙的避免结尾的空格影响AC。
这道题跟单纯的TSP问题区别就在于TSP是对于无向赋权图来说找出最短的哈密顿回路，而这道题是对于有向无权图来说的（为什么是有向的，这是因为主客场制出现A在主场赢了B，A在客场也赢了B的情况）。当然剪枝之后效率会更好，但是蒟蒻的我还是不要把自己越搞越迷糊的好。

import java.util.Scanner;public class Main {static boolean[][] a;static int n;static int cnt = 0;static int flag = 0;static int[] res;static boolean[] vis;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();a = new boolean[n + 1][n + 1];vis = new boolean[n + 1];res = new int[n + 1];/*** 注意nextLine()会读取上一个回车* */ for (int i = 0; i <= n; i++) {String s = in.nextLine();for (int j = 0; j < s.length(); j++) {if (s.charAt(j) == 'W') {a[i][j+1] = true;} if (s.charAt(j) == 'L'){a[j+1][i] = true;}}}f(1, 1);if (flag == 1) {for (int i = 1; i <= n; i++) {System.out.print(i == 1 ? "" : " ");System.out.print(res[i]);}} else {System.out.println("No Solution");}}private static void f(int cur, int num) {if (flag == 1) {return;}res[cur] = num;if (cur == n && a[num][1] == true) {flag = 1;return;}if (cur == n) {return; }vis[num] = true;for (int i = 1; i <= n; i++) {if (vis[i] == false && a[num][i] == true) {f(cur + 1, i);}}vis[num] = false;} }

总结

以上是生活随笔为你收集整理的PAT L3-015 ---- 球队“食物链”(DFS)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。