您的位置: 首页  >  文章  >  PAT TOP 1012 Greedy Snake （35）

PAT TOP 1012 Greedy Snake （35）

分类: 文章 • 2023-03-16 21:37:45

问题描述：

1012 Greedy Snake （35 分）

Have you ever played the game "Greedy Snake"? In the game, we control the movements of the snake to eat the fruits scattered in the game field, while the snake's body gets longer whenever it eats a fruit. The goal of the game is to make the snake eat as many fruits as possible, before its head has no where to go. It would be a real challenge to let you program this game, right now.

PAT TOP 1012 Greedy Snake （35）

But hey! Relax! This time you are only asked to program a simplified version of the game. In this simple version, the fruits are all over the place except at some extra obstacle cells. The snake's body will extend all the way along the path while it eats the fruits. You may take any fruit cell as the starting position of the snake. Then you have four directions to choose from: UP, DOWN, LEFT or RIGHT. Once you pick up a direction for the snake, it must keep going until it hits an obstacle or its own body. This procedure repeats until the head of the snake has no where to go -- that is, every adjacent cell of its head is either an obstacle or its own body. Your task is to minimize the number of fruits left.

For example, let's define the game field to be a 6 by 6 maze, surrounded by obstacle cells #, with one extra obstacle @. S is the starting position of the snake. All the fruits are represented by dots.

######
#[email protected]#
#....#
#....#
#....#
######

Then if you decide to move DOWN, RIGHT, and UP, the results are shown below.

######
#..*@#
#..*.#
#..*.#
#..S.#
######

######
#..*@#
#..*.#
#..*.#
#..*S#
######

######
#..*@#
#..*S#
#..**#
#..**#
######

Now the snake is stucked, the game is over, and there are 8 fruits left. However, by carefully changing your moves or choosing another starting position, you can actually control the snake to eat up all the fruits. Try it out!

Task 1: minimize the number of fruits left, and count the number of starting positions that can lead to the optimal solution.

Task 2: To make things more interesting, you may replace one fruit cell by an obstacle, to obtain a better result, and count the number of ways to add an obstacle that leads to the better result. In case there is no way to improve the result by adding one obstacle, you should point out this situation.

Input Specification:

Each input file contains one test case. For each case, the first line contains two integers N (4≤N≤15), the size of the game field, and K (0≤K≤2), the number of extra obstacles. Then K lines follow, each gives the coordinates of an obstacle in the format "x​i​​ y​i​​" where 2≤x​i​​,y​i​​≤N−1.

Output Specification:

For each case, print the results in two lines. In the first line print the minimal number of fruits left, and the number of different optimal starting positions. Then in the second line, either print −1 if there is no way to improve the result, or two integers: the better result and the number of optimal ways to add an obstacle.

Sample Input 1:

6 1
2 5

Sample Output 1:

0 4
-1

Sample Input 2:

6 2
2 2
3 3

Sample Output 2:

2 1
0 2

 

走迷宫首选深度优先搜索算法。在本题的深度优先搜索函数void dfs(int p,int vp,int l)中维护了三个变量，即当前蛇的位置p，速度vp，剩余的水果l。每次确定了速度vp之后，便要一直走到下一跳为墙壁时再选择下一次的速度。

本来以为不剪枝地直接搜索会爆出运行超时，结果意外地AC了。顺便一说，第一个和最后一个测试点的第二行是要输出-1的。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,lp;
vector<bool> v;
void dfs(int p,int vp,int l)
{
	if(vp&&v[p+vp])
	{
		v[p]=false;
		dfs(p+vp,vp,l-1);
		v[p]=true;
	}
	else
	{
		if(v[p-n])
		dfs(p,-n,l);
		if(v[p-1])
		dfs(p,-1,l);
		if(v[p+1])
		dfs(p,1,l);
		if(v[p+n])
		dfs(p,n,l);
		lp=min(lp,l);
	}
}
int main()
{
//	freopen("data.txt","r",stdin);
	scanf("%d %d",&n,&m);
	int lf=(n-2)*(n-2)-m;
	vector<int> vr(lf,0);
	v.resize(n*n,true);
	for(int i=0;i<n;i++)
	{
		v[i]=false;
		v[i*n]=false;
		v[i*n+n-1]=false;
		v[(n-1)*n+i]=false;
	}
	int x,y;
	for(int i=0;i<m;i++)
	{
		scanf("%d %d",&x,&y);
		x--;
		y--;
		v[x*n+y]=false;
	}
	for(int i=0;i<n*n;i++)
	{
		if(v[i])
		{
			lp=lf-1;
			dfs(i,0,lf-1);
			vr[lp]++;
		}
	}
	int bst=0;
	for(int i=0;i<lf;i++)
	{
		if(vr[i])
		{
			bst=i;
			printf("%d %d\n",i,vr[i]);
			break;
		}
	}
	
	vector<int> vbr(bst,0);
	lf--;
	for(int i=0;i<n*n;i++)
	{
		if(v[i])
		{
			v[i]=false;
			lp=lf-1;
			for(int j=0;j<n*n;j++)
			if(v[j]) dfs(j,0,lf-1);
			if(lp<bst) vbr[lp]++;
			v[i]=true;
		}
	}
	bool bbst=true;
	for(int i=0;i<bst&&bbst;i++)
	{
		if(vbr[i])
		{
			printf("%d %d",i,vbr[i]);
			bbst=false;
		}
	}
	if(bbst) printf("-1");
	return 0;
}

 

相关推荐