本文主要是介绍K King of the Waves，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
K King of the Waves
You are organising a king of the hill tournament, the Buenos AiresPaddleboarding Competition (BAPC), with n participants. In aking of the hill tournament, one person starts as a “king” and isthen challenged by another person, the winning person becomesthe new king. This is repeated until all participants have challengedexactly once (except for the starting person). In a paddleboardingmatch, there are no draws. The person which ends up asking, wins the tournament. Since you are the organiser, you get tochoose the starting person and the order in which they challengethe king.
Someone is offering you a substantial amount of money in caseone of the participants, Henk, ends up winning the tournament. You happen to know, forany two participants x and y, which of the two would win if they were to match during thetournament. Consequently, you choose to do the unethical: you will try to rig the game. Canyou find a schedule that makes Henk win the tournament?
Input
• The first line contains an integer 1 ≤ n ≤ 1000, the number of participants. Theparticipants are numbered 0, . . . , n − 1, where Henk is 0.
• Then n lines follow, where each line has exactly n characters (not counting the newlinecharacter). These lines represent the matrix with the information of who beats who, asfollows. On line i the jth character is (note that 0 ≤ i, j < n):
– ’1’ if person i will win against person j.
– ’0’ if person i will lose against person j.
– ’X’ if i = j.
Output
Print a sequence of participants, such that the first person starts as king and the consequentparticipants challenge the king. If there is no way to rig the game such that Henk wins, print“impossible”.
题意：
给你n,代表有0 n-1个人,给你n行,每行n个字符,字符是X,i=j就是这个人在这个位置
1 代表,i人能赢j人当king
0代表输;
游戏规则是b 是king a能赢b a当king
问裁判按什么安排顺序0能当king
dfs遍历复杂时，可看看题意是否把握好。比如这题，“如何安排顺序使得0能最终获胜”，加入顺序为k1 k2 k3 k4……k1到k2可不是k1指向k2哦！还可以是k2指向k1.（k2 来挑战k1，只不过失败了而已）
思路：
a->b:a能打败b
查找0能打败的，每条支路继续往下搜。
eg:0->2->1->3
0->4
0->5->6
不管3、4、6谁能打败谁，0一定能打败它们仨。
代码：
#include<iostream>
#include<cstring>
using namespace std;int n,k,flag;
char s[1005];
int vis[1005];
int a[1005][1005];
int b[1005];void dfs(int h)
{if(k==n-1){flag=1;return;}else{for(int i=0;i<n;i++){if(a[h][i]&&!vis[i]){vis[i]=1;b[k++]=i;dfs(i);}}}
}int main()
{cin>>n;flag=0;k=0;for(int i=0;i<n;i++){cin>>s;for(int j=0;j<n;j++){if(s[j]=='1')a[i][j]=1;elsea[i][j]=0;}}memset(vis,0,sizeof(vis));vis[0]=1;dfs(0);if(flag){for(int i=k-1;i>=0;i--)cout<<b[i]<<" ";cout<<"0"<<endl;}elsecout<<"impossible"<<endl;return 0;
}
这篇关于K King of the Waves的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
