[JLOI2010] 世界杯租房
题目描述
南非世界杯组委会指定了在此期间可提供的一些旅馆供球迷租赁，名为阿凡达的即是其中一所。因为阿凡达旅馆房子的数目不超过262626，所以它们可以用262626个大写字母表示。
有一天，刘经理的电话响了，他接到了一个租赁房屋的请求，要求从666月121212日晚起租到666月191919日中午。于是他察看了预定表，但是并没有发现一间房屋能够直接满足要求。比如房主可能因为一些私人原因需要留在自己的房子中，所以这个游客不得不在其中的一间先住上几天再搬到另一间住上几天。他详细检查了预定表后，对旅客说：“我将你先在BBB安置333天，再将你安排到FFF去度过剩余的旅途。”
你的目标是使得游客从一间房屋搬到另一间房屋的次数最少。
注意在旅馆的计费中，总是将某一天的晚上到第二天的中午视作一天。
输入格式
输入文件包括多组数据。每组数据输入文件第一行包括两个整数MMM和NNN。MMM表示日程表上的天数，NNN表示公寓的数目。天数不超过100100100天，从1开始计数，公寓不超过262626个，从AAA开始计数。
接下来MMM行，每行包括NNN个字母，表示从第i天晚到次日中午，该公寓是否已经被出租，XXX代表被出租，OOO代表未被出租。
最后一行包括两个整数s,ts,ts,t，代表旅客从第sss天晚入住到第(t+1)(t+1)(t+1)天中午结束旅行。1≤s M=N=0M=N=0M=N=0标志着文件的结束。 输出格式 对于每一组数据，首先打印测试数据的编号，冒号和一个空行。接下来输出换房次数最少的方案，每一行使用如下格式： 其中 注意，如果存在多种方案满足换房次数最少，输出其中字典序最小的方案。 如不存在这样的方案，输出一行”Not availableNot\ availableNot available”。 每两组输出之间以一个空行隔开。输出文件的末尾不要加空行。 10 7 XXXXXXX XOXXXXO XOXXXXO XOXXXOX OXXOXOX XOXOXOX OXXOXOX OXXXXOX XXXXXXX XXXXXXX 2 9 0 0 Case 1: B: 2-5 F: 5-9