球队“食物链“

cpp代码

#include <iostream>
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('
');
}

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
");
	}
	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();
	}
}

========================================Talk is cheap, show me the code=======================================