HDU2821 Pusher HDU3500 Fling DFS搜尋

Pusher

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/65536 K (Java/Others)

Total Submission(s): 169 Accepted Submission(s): 67

Special Judge

Problem Description PusherBoy is an online game http://www.hacker.org/push . There is an R * C grid, and there are piles of blocks on some positions. The goal is to clear the blocks by pushing into them.

You should choose an empty area as the initial position of the PusherBoy. Then you can choose which direction (U for up, D for down, L for left and R for right) to push. Once the direction is chosen, the PusherBoy will walk ahead until he met a pile of blocks (Walking outside the grid is invalid). Then he remove one block from the pile (so if the pile contains only one block, it will become empty), and push the remaining pile of blocks to the next area. (If there have been some blocks in the next area, the two piles will form a new big pile.)

Please note if the pusher is right up against the block, he can't remove and push it. That is, there must be a gap between the pusher and the pile. As the following figure, the pusher can go up, but cannot go down. (The cycle indicates the pusher, and the squares indicate the blocks. The nested squares indicate a pile of two blocks.)

And if a whole pile is pushed outside the grid, it will be considered as cleared.

Input There are several test cases in each input. The first two lines of each case contain two numbers C and R. (R,C <= 25) Then R lines follow, indicating the grid. '.' stands for an empty area, and a lowercase letter stands for a pile of blocks. ('a' for one block, 'b' for two blocks, 'c' for three, and so on.)

Output Output three lines for each case. The first two lines contains two numbers x and y, indicating the initial position of the PusherBoy. (0 <= x < R, 0 <= y < C). The third line contains a moving sequence contains 'U', 'D', 'L' and 'R'. Any correct answer will be accepted.

Sample Input

3
7
...
...
.b.
...
...
.a.
...
        

Sample Output

4
1
UDU

   
    
     Hint
    
Hint: The following figures show the sample. The circle is the position of the pusher. 
And the squares are blocks (The two nested squares indicating a pile of two blocks). And this is the unique solution for this case.

   
    

   
    
        
  
        

Source 2009 Multi-University Training Contest 1 - Host by TJU

Recommend gaojie   建議先去玩玩這個遊戲^_^ 題意：n*m的格子上有一些方塊放在某些格子上，一個格子可能有幾個方塊，用'a'-'z'來表示方塊數量。 初始的時候可以選擇任意空地作為Pusher初始點，Pusher選擇一個方向，然後向這個方向前進直到遇到有方塊的格子，Pusher把這個格子的方塊清除一個，并把它向前推一格（向前不能出界），如果前面一格有方塊，那麼這些方合起來放在這個格子中。Pusher和有方塊的格子之間至少要有一個空地才能推動。 題解： 就是赤裸裸的DFS搜尋，不過要注意一些細節。 枚舉每一個有方塊的格子周圍距離為2的空地作為初始點， 枚舉方向推動Pusher，注意回溯時要還原狀态。 代碼：

#include<cstdio>
#include<cstring>
#include<cctype>

int n,m,num,cnt,a[35][35],dir[4][2]={0,-1,0,1,-1,0,1,0};
char map[35][35],p[]="LRUD",path[625];
int ok(int x,int y)
{
	if(x<0||y<0||x>=n||y>=m)
		return 0;
	if(a[x][y]==0)
		return 1;
	return -1;
}
int dfs(int x,int y,int pos)
{
	int i,xx,yy,tx,ty;
	for(i=0;i<4;i++)
	{
		xx=x+dir[i][0];
		yy=y+dir[i][1];
		if(ok(xx,yy)!=1)
			continue;
		do
		{
			xx+=dir[i][0];
			yy+=dir[i][1];
		}while(ok(xx,yy)==1);
		if(ok(xx,yy)&&ok(tx=xx+dir[i][0],ty=yy+dir[i][1])&&a[xx][yy])
		{
			int t=a[xx][yy];
			path[pos]=p[i];
			if(t==1||a[tx][ty])
				cnt--;
			if(cnt==0)
			{
				num=pos;
				return 1;
			}
			a[tx][ty]+=t-1;
			a[xx][yy]=0;
			if(dfs(xx,yy,pos+1))
				return 1;
			a[xx][yy]=t;
			a[tx][ty]-=t-1;
			if(t==1||a[tx][ty])
				cnt++;
		}
	}
	return 0;
}
int main()
{
	while(~scanf("%d%d",&m,&n))
	{
		int i,j,k,x,y,flag=1,f[35][35]={0};
		for(i=num=0;i<n;i++)
		{
			scanf("%s",map[i]);
			for(j=0;j<m;j++)
				if(isalpha(map[i][j]))
					num++,a[i][j]=map[i][j]-'a'+1;
				else
					a[i][j]=0;
		}
		for(i=0;i<n&&flag;i++)
			for(j=0;j<m&&flag;j++)
				if(a[i][j])
					for(k=0;k<4&&flag;k++)
					{
						x=i+dir[k][0]*2;
						y=j+dir[k][1]*2;
						if(ok(x,y)>0&&!f[x][y])
						{
							f[x][y]=1;
							cnt=num;
							if(dfs(x,y,0))
								flag=0;
						}
					}
		printf("%d\n%d\n",x,y);
		for(i=0;i<=num;i++)
			printf("%c",path[i]);
		puts("");
	}
}
           

Fling

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)

Total Submission(s): 227 Accepted Submission(s): 96

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 &#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.

Input 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.

Output For each case, print a line formatted as "CASE #NUM:", where NUM is the number of current case.

Then every &#180;fling&#180; 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<cstdio>
#include<cstring>

int t,n=7,m=8,num,dir[4][2]={-1,0,0,-1,0,1,1,0};
int path[15],f[15];
char map[15][15],p[]="ULRD",pathc[15];
int ok(int x,int y)
{
	if(x<0||y<0||x>=n||y>=m)
		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<n;i++)
		for(j=0;j<m;j++)
			if(map[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(map[x][y]=='O')
						continue;
					while(ok(x,y))
					{
						if(map[x][y]=='O')
						{
							flag=1;
							tx[cnt]=x;
							ty[cnt++]=y;
						}
						x+=dir[k][0];
						y+=dir[k][1];
					}
					if(flag)
					{
						map[i][j]='X';
						for(int ii=0;ii<cnt;ii++)
						{
							map[tx[ii]][ty[ii]]='X';
							map[tx[ii]-dir[k][0]][ty[ii]-dir[k][1]]='O';
						}
						path[pos]=i*m+j;
						pathc[pos]=p[k];
						if(dfs(pos+1))
							return 1;
						map[i][j]='O';
						x=i+dir[k][0];
						y=j+dir[k][1];
						while(ok(x,y))
						{
							if(map[x][y]=='O')
								map[x][y]='X';
							x+=dir[k][0];
							y+=dir[k][1];
						}
						for(int ii=0;ii<cnt;ii++)
							map[tx[ii]][ty[ii]]='O';
					}
				}
	return 0;
}
int main()
{
	while(~scanf("%s",map[0]))
	{
		int i,j;
		num=0;
		memset(f,0,sizeof(f));
		for(i=1;i<n;i++)
			scanf("%s",map[i]);
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
				if(map[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]/m,path[i]%m,pathc[i]);
	}
}