Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom5月前

04/5
14:35
二分图匹配 博弈论

[bzoj 1443] [JSOI2009]游戏Game

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

输入数据首先输入两个整数N,M,表示了迷宫的边长。 接下来N行,每行M个字符,描述了迷宫。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

若小AA能够赢得游戏,则输出一行"WIN",然后输出所有可以赢得游戏的起始位置,按行优先顺序输出 每行一个,否则输出一行"LOSE"(不包含引号)。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

3 3
.##
...
#.#

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

WIN
2 3
3 2

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

对于100%的数据,有1≤n,m≤100。 对于30%的数据,有1≤n,m≤5。

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

二分图博弈,先把最大匹配给求出来。然后对于一个非匹配点,把棋子放置在这里,那么对于之后的每一步,小AA都可以走YY走的点的匹配点,由于最大匹配是没有増广路的,所以非匹配点必胜。同理,对于从任意一个非匹配点走2步可以走到的匹配点也是必胜点。

 

[bzoj 1443] [JSOI2009]游戏Game