球队“食物链“

cpp代码

#include 
using namespace std;
const int INF = 10000000;
int N;
char match[22][22];
int used[22];
int flag, flagrow = 1;
int d[22];
int win[22];
void output()
{printf("%d", d[1]);for (int i = 2; i <= N; ++i){printf(" %d", d[i]);}putchar('\n');
}int pruning(int k, int i)
{int j; if (flag)	return 0;if (k > 1 && match[d[k - 1]][i] != 'W' && match[i][d[k - 1]] != 'L')	return 0;if (k == N && match[i][d[1]] != 'W' && match[d[1]][i] != 'L')	return 0;if (used[i])	return 0;//访问过跳出 //未访问过的队伍有没有赢过1的，即有没有回路 for (j = 1; j <= N ;++j){if (!used[j] && (match[j][1] == 'W' || match[1][j] == 'L')){break;//成功，可以继续回路到1}}if (j > N)	return 0;//失败，未访问过的队伍有没有赢过1的，剪枝 return 1;
}void f(int k)
{if (k - 1 == N){output();flag = 1;}else{for (int i = 1; i <= N; ++i){if (pruning(k, i)){d[k] = i;used[i] = 1;f(k + 1);used[i] = 0;}}}
}int main()
{scanf("%d", &N);getchar();for (int i = 1; i <= N; ++i){gets(match[i] + 1);d[i] = INF;}for (int i = 1; i <= N; ++i){for (int j = 1; j <= N; ++j){if (match[i][j] == 'W' || match[j][i] == 'L')	++win[i];}}//回溯之前剪枝for (int i = 1; i <= N; ++i){if (!win[i])//有一队没有赢过 {flagrow = 0;break;}}if (flagrow)	f(1);if (!flagrow || !flag){printf("No Solution\n");}return 0;
}

java代码

import java.util.Scanner;public class Main
{public static final int INF = 10000000;public static int N;public static char[][] match = new char[22][22];public static int[] used = new int[22];public static int flag, flagrow = 1;public static int[] d = new int[22];public static int[] win = new int[22];public static void main(String[] args){Scanner cin = new Scanner(System.in);N = cin.nextInt();for (int i = 1; i <= N; ++i){String str = cin.next();for (int j = 1; j <= N; ++j){match[i][j] = str.charAt(j - 1);}d[i] = INF;}cin.close();for (int i = 1; i <= N; ++i){for (int j = 1; j <= N; ++j){if (match[i][j] == 'W' || match[j][i] == 'L'){++win[i];//第i队赢过的次数}}}//回溯之前剪枝for (int i = 1; i <= N; ++i){if (win[i] == 0)//有一队没赢过{flagrow = 0;break;}}if (flagrow == 1)	f(1);if (flagrow == 0 || flag == 0){System.out.println("No Solution");}}public static void f(int k){if (k > N){output();flag = 1;}else{for (int i = 1; i <= N; ++i){if (pruning(k, i)){d[k] = i;used[i] = 1;f(k + 1);used[i] = 0;}}}}public static boolean pruning(int k, int i){if (flag == 1)	return false;//输出过一次了if (k > 1 && match[d[k - 1]][i] != 'W' && match[i][d[k - 1]] != 'L')	return false;if (k == N && match[i][d[1]] != 'W' && match[d[1]][i] != 'L')	return false;if (used[i] == 1)	return false;int j;for (j = 1; j <= N; ++j)//未访问过的队伍有没有赢过1的，即有没有回路{if (used[j] == 0 && (match[j][1] == 'W' || match[1][j] == 'L')){break;//成功，可以继续回路到1}}if (j > N)//失败，未访问过的队伍有没有赢过1的，剪枝 {return false;}return true;}public static void output(){System.out.print(d[1]);for (int i = 2; i <= N; ++i){System.out.print(" " + d[i]);}System.out.println();}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！