2014
04-09

# Fling

Fling is a kind of puzzle games available on phone.
This game is played on a board with 7 rows and 8 columns. Each puzzle consists of a set of furballs placed on the board. To solved a puzzle, you need to remove the furballs from board until there is no more than one furball on the board. You do this by &#180;flinging&#180; furballs into other furballs, to knock them off the board. You can fling any furballs in four directions (up, left, right, down). The flung furball stops at the front grid of another one as soon as knocking it. And the knocked furball continues to rolling in the same direction until the last knocked one goes off the board. For instance, A furball at (0, 0) rolls right to the furball at (0, 5), then it will stop at (0, 4). Moreover, the latter will roll to right. You cannot fling a furball into a neighbouring furball, the one next to in any of four directions. However, it is permitted for a rolling ball knocks into a ball with a neighbour in that direction.

The input contains multiple test cases.
For each case, the 7 lines with 8 characters describe the board. &#180;X&#180; represents a empty grid and &#180;O&#180; represents a grid with a furball in it. There are no more than 12 furballs in any board.
Each case separated by a blank line.

The input contains multiple test cases.
For each case, the 7 lines with 8 characters describe the board. &#180;X&#180; represents a empty grid and &#180;O&#180; represents a grid with a furball in it. There are no more than 12 furballs in any board.
Each case separated by a blank line.

XXXXXXXX
XXOXXXXX
XXXXXXXX
XXXXXXXX
XOXXXXOX
XXXXXXXX
XXXXXXXX

XXXXXXXX
XOXOXOOX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX

CASE #1:
4 6 L
1 2 D

CASE #2:
1 1 R
1 4 L
1 3 R

#include <cstdio>
#define MAX 8
using namespace std;
char map[7][MAX];
char s[11][MAX];
int n,flag,total;
struct node{
int i,j;
int run;
}road[11];
bool judge(int curi,int curj,int x)              //判断是否可推函数，长了Debug好痛苦。。。
{
int i;
if(x==1){
if(curi-1<0||(map[curi-1][curj]=='O'))
return 0;
for(i=2;curi-i>=0;i++)
if(map[curi-i][curj]=='O')
return 1;
}else if(x==2){
if(curj-1<0||(map[curi][curj-1]=='O'))
return 0;
for(i=2;curj-i>=0;i++)
if(map[curi][curj-i]=='O')
return 1;
}else if(x==3){
if(curj+1>=8||(map[curi][curj+1]=='O'))
return 0;
for(i=2;curj+i<8;i++)
if(map[curi][curj+i]=='O')
return 1;
}else if(x==4){
if(curi+1>=7||(map[curi+1][curj]=='O'))
return 0;
for(i=2;curi+i<7;i++)
if(map[curi+i][curj]=='O')
return 1;
}
return 0;
}
void dfs(){
int i,j,k,l,l2;
if(total==n){
for(i=1;i<total;i++){
printf("%d %d ",road[i].i,road[i].j);
if(road[i].run==1)
printf("U\n");
else if(road[i].run==2)
printf("L\n");
else if(road[i].run==3)
printf("R\n");
else if(road[i].run==4)
printf("D\n");
}
flag=1;
return ;
}
for(i=0;i<7;i++){
for(j=0;j<8;j++){
if(map[i][j]=='O'){
for(k=1;k<=4;k++){
if(!judge(i,j,k))continue;
road[total].i=i;
road[total].j=j;
road[total].run=k;
if(k==1||k==4){
for(l=0;l<7;l++){
s[total][l]=map[l][j];            //该列改变了，记录该列。
}
}
else{
for(l=0;l<8;l++){
s[total][l]=map[i][l];           //该行改变了，记录该行。
}
}
map[i][j]='X';
if(k==1){                                //分类讨论推动方向
l2=i;
for(l=i-1;l>=0;l--){
if(map[l][j]=='O'){
map[l+1][j]='O';
if(l2!=l+1){
map[l2][j]='X';
}
l2=l;
}
}
map[l2][j]='X';
}else if(k==2){
l2=j;
for(l=j-1;l>=0;l--){
if(map[i][l]=='O'){
map[i][l+1]='O';
if(l2!=l+1){
map[i][l2]='X';
}
l2=l;
}
}
map[i][l2]='X';
}else if(k==3){
l2=j;
for(l=j+1;l<8;l++){
if(map[i][l]=='O'){
map[i][l-1]='O';
if(l-1!=l2){
map[i][l2]='X';
}
l2=l;
}
}
map[i][l2]='X';
}else if(k==4){
l2=i;
for(l=i+1;l<7;l++){
if(map[l][j]=='O'){
map[l-1][j]='O';
if(l-1!=l2){
map[l2][j]='X';
}
l2=l;
}
}
map[l2][j]='X';
}
total++;
dfs();
if(flag)return ;
total--;
if(k==1||k==4){                         //进行回溯。
for(l=0;l<7;l++){
map[l][j]=s[total][l];
}
}
else{
for(l=0;l<8;l++){
map[i][l]=s[total][l];
}
}
}
}
}
}
}
int main()
{
int casi=0;
int i,j;
while(scanf("%s",s[0])!=EOF){
if(casi)printf("\n");
n=0;
for(i=0;i<8;i++){
map[0][i]=s[0][i];
if(map[0][i]=='O')
n++;
}
for(i=1;i<7;i++){
scanf("%s",s[0]);
for(j=0;j<8;j++){
map[i][j]=s[0][j];
if(map[i][j]=='O')
n++;
}
}
flag=0;
total=1;
printf("CASE #%d:\n",++casi);
dfs();
}
return 0;
}

234MS过的，速度不错。但是因为代码长因此Debug了很久，这题思路就是简单的搜每个点看其能不能推，能推就搜，失败了就回溯。

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

3. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮