hdu4925Apple Tree(找规律)

题目:hdu4925Apple Tree(找规律)


题目大意:给出N* M 的矩阵,然后每个格子要不种苹果,要不施肥:在(X,Y)施肥后,它上下左右的苹果树的产量会翻倍。种了苹果数,产量为1.求这样的N * M个矩阵能得到的最大的苹果数。


解题思路:

                对于2 * 2的矩阵: X代表施肥 , 有数字代表种树  X 2  这样是最好的。各自上的数字代表这个格子被施肥几次。那么2 * 2的最多的苹果数 2 ^2 + 2^2 = 8;

                                                                                                     2 X      

                 3 * 3 : X  3 X

                             3  X   3

                             X  3    X      4 * 2^3  = 32;

                发现规律:第一行第一个都是拿来施肥的,每次从第一行的第2个开始查找,它上下左右的各自都拿来施肥,这样能够最大化的影响它的产量,产量2^N(上下左右的格子个数),并且施肥的地方要标记一下,下次不能在这里种树。这样往后找,最后得到总产量。


代码:

#include <cstdio>
#include <cstring>

const int N = 105;
const int M = 4;
int visit[N][N];
const int dir[M][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

int main () {

	int t;
	int n, m;
	int ans, temp;
	scanf ("%d", &t);
	while (t--) {

		scanf ("%d%d", &n, &m);

		memset (visit, 0, sizeof(visit));
		visit[0][0] = 1;
		ans = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {

				if (visit[i][j])
					continue;
				temp = 0;
				for (int k = 0; k < M; k++) {
					
					if (i + dir[k][0] >= 0 && i + dir[k][0] < n && j + dir[k][1] >= 0 && j + dir[k][1] < m) {

						temp++;
						visit[i + dir[k][0]][j + dir[k][1]] = 1;
					}
				}
				ans += 1<<temp;
			}

		if (!ans)
			printf ("1\n");
		else
			printf ("%d\n", ans);
	}
	return 0;
}


hdu4925Apple Tree(找规律),布布扣,bubuko.com

hdu4925Apple Tree(找规律)

上一篇:移动互联网教育领域或将出现新的风口?


下一篇:探寻ASP.NET MVC鲜为人知的奥秘(1):对LESS的支持