首页 > 搜索 > DFS搜索 > hdu 2182 Frog-DFS-[解题报告]C++
2013
12-30

hdu 2182 Frog-DFS-[解题报告]C++

Frog

问题描述 :

A little frog named Fog is on his way home. The path’s length is N (1 <= N <= 100), and there are many insects along the way. Suppose the
original coordinate of Fog is 0. Fog can stay still or jump forward T units, A <= T <= B. Fog will eat up all the insects wherever he stays, but he will
get tired after K jumps and can not jump any more. The number of insects (always less than 10000) in each position of the path is given.
How many insects can Fog eat at most?
Note that Fog can only jump within the range [0, N), and whenever he jumps, his coordinate increases.

输入:

The input consists of several test cases.
The first line contains an integer T indicating the number of test cases.
For each test case:
The first line contains four integers N, A, B(1 <= A <= B <= N), K (K >= 1).
The next line contains N integers, describing the number of insects in each position of the path.

输出:

The input consists of several test cases.
The first line contains an integer T indicating the number of test cases.
For each test case:
The first line contains four integers N, A, B(1 <= A <= B <= N), K (K >= 1).
The next line contains N integers, describing the number of insects in each position of the path.

样例输入:

1
4 1 2 2 
1 2 3 4 

样例输出:

8

题目链接:here

分析:很简单一个搜索。。。直接暴搜即可。。不知道为啥夏天的风把他分类到level1.。。。

代码:

#include <iostream>
#include <cstdio>
using namespace std;

int ansnum;
int neigh[22][3];
bool vis[22];
int state[22];
int m;

void dfs(int x, int num)
{
	int i, j;

	if (num == 20)
	{
		bool flag = false;
		for (i=0; i<3; i++) if (neigh[x][i] == m) flag = true;
		if (flag)
		{
			ansnum ++;
			printf("%d: ", ansnum);
			for (j=0; j<20; j++) printf(" %d", state[j]);
			printf(" %d\n", m);
		}
		return ;
	}

	for (i=0; i<3; i++)
	{
		if (!vis[neigh[x][i]])
		{
			state[num] = neigh[x][i];
			vis[neigh[x][i]] = true;

			dfs(neigh[x][i], num+1);
			
			vis[neigh[x][i]] = false;
		}
	}
}

int main()
{
	int i;
	for (i=1; i<=20; i++)
	{
		scanf("%d %d %d", &neigh[i][0], &neigh[i][1], &neigh[i][2]);
	}
	while (scanf("%d", &m), m)
	{
		ansnum = 0;
		memset(vis, false, sizeof(vis));
		vis[m] = true;
		state[0] = m;
		dfs(m, 1);
	}
	return 0;
}

解题转自:http://blog.csdn.net/liuqiyao_01/article/details/8858168


,
  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  3. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  4. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.