Problem Description
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 ´flinging´ 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.
Input
The input contains multiple test cases.
For each case, the 7 lines with 8 characters describe the board. ´X´ represents a empty grid and ´O´ 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.
Output
For each case, print a line formatted as "CASE #NUM:", where NUM is the number of current case.
Then every ´fling´ prints a line. Each line contains two integers X, Y and a character Z. The flung furball is located at grid (X, Y), the top-left grid is (0, 0). And Z represents the direction this furball towards: U (Up), L (Left), R (Right) and D (Down);
Print a blank line between two cases.
You can assume that every puzzle could be solved.
If there are multiple solve sequences, print the smallest one. That is, Two sequences A (A1, A2, A3 ... An) and B (B1, B2, B3 ... Bn). Let k be the smallest number that Ak != Bk.
Define A < B :
(1) X in Ak < X in Bk;
(2) Y in Ak < Y in Bk and X in Ak = X in Bk;
(3) Z in Ak < Z in Bk and (X,Y) in Ak = (X,Y) in Bk;
The order of Z: U < L < R < D.
Sample Input
XXXXXXXX
XXOXXXXX
XXXXXXXX
XXXXXXXX
XOXXXXOX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XOXOXOOX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
Sample Output
CASE #1:
4 6 L
1 2 D
CASE #2:
1 1 R
1 4 L
1 3 R
Author
EvilSeraph
Source
2010 ACM-ICPC Multi-University Training Contest（7）——Host by HIT
Recommend
zhouzeyong
首先，先简单介绍一下这款游戏！游戏中，会有几颗毛球随意摆放在方格中，玩家必须找出正确的滚球顺序，然后将毛球们一一相互撞击出方格外，留下最后一颗毛球才算成功过关。在同一行或同一列的毛球才能彼此撞击，但紧靠在一起的两颗毛球是无法移动的哦！两者中间一定要留下至少一个空格才行，如果撞击的顺序不对，最后剩下的毛球都不在同一行列上或是相连的话，就无法继续下个关卡。模仿一个大佬的代码写的！！！！在输出问题上一直有点小问题！
代码：
#include<bits/stdc++.h>
using namespace std;
int t=0,num,dir[4][2]={-1,0,0,-1,0,1,1,0};
int path[15],f[15];
char map1[15][15],p[5]="ULRD",pathc[15];
bool ok(int x,int y)
{
if(x<0||y<0||x>=7||y>=8)
return 0;
return 1;
}
int dfs(int pos)
{
if(pos==num-1)
return 1;
int i,j,k,x,y,tx[15],ty[15];
for(i=0;i<7;i++)
for(j=0;j<8;j++)
if(map1[i][j]=='O')
for(k=0;k<4;k++)
{
int flag=0,cnt=0;
x=i+dir[k][0];
y=j+dir[k][1];
if(map1[x][y]=='O')
continue;
while(ok(x,y))
{
if(map1[x][y]=='O')
{
flag=1;
tx[cnt]=x;
ty[cnt++]=y;
}
x+=dir[k][0];
y+=dir[k][1];
}
if(flag)
{
map1[i][j]='X';
for(int ii=0;ii<cnt;ii++)
{
map1[tx[ii]][ty[ii]]='X';
map1[tx[ii]-dir[k][0]][ty[ii]-dir[k][1]]='O';
}
path[pos]=i*8+j;
pathc[pos]=p[k];
if(dfs(pos+1))
{
return 1;
}
map1[i][j]='O';
x=i+dir[k][0];
y=j+dir[k][1];
while(ok(x,y))
{
if(map1[x][y]=='O')
map1[x][y]='X';
x+=dir[k][0];
y+=dir[k][1];
}
for(int ii=0;ii<cnt;ii++)
map1[tx[ii]][ty[ii]]='O';
}
}
return 0;
}
int main()
{
freopen("a.txt","r",stdin);
ios::sync_with_stdio(false);
while(cin>>map1[0])
{
int i,j;
num=0;
memset(f,0,sizeof(f));
for(i=1;i<7;i++)
cin>>map1[i];
for(i=0;i<7;i++)
for(j=0;j<8;j++)
if(map1[i][j]=='O')
num++;
dfs(0);
if(t)
puts("");
printf("CASE #%d:\n",++t);
for(i=0;i<num-1;i++)
printf("%d %d %c\n",path[i]/8,path[i]%8,pathc[i]);
}
}
自己并没有把这个题看明白消化掉，还有很长的路要走啊！尚未成功，仍需努力
