华为七月份机试题总结2-0714

/*
华为的机试题0714-1：
感觉和岛屿的个数是一样的 
题目： 
第蜂巢形状的区域相连(M*N)，输入中只有C(Clean)和P(Pollution)两种数据，要求输入未被污染的区域数量
注意是蜂巢
上下，左右，左下，右上一共6个方向。 
	* *
  * # *
  * *
这样正好是一个六边形

实际上其他方向也可以例如（上下，左右，左下，右上），只要保证是6个方向就可以（发现不行，
蜂巢的方向究竟是怎么确定的，题目上有没有详细的说明？？？） 

  * * 
  * # *
    * *
输入： 
第一行输入：m, n  （m行n列）
依次输入每一行的数据 
4 4
C C P P
P C P C
P P P C
C C C P
输出： 2
*/ 
#include<bits/stdc++.h>
using namespace std;

void dfs(vector<vector<char>> &graph, int i, int j)
{
	if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[i][j] == 'P')
	{
		return;
	}
	graph[i][j] = 'P';
	dfs(graph, i+1, j);
	dfs(graph, i-1, j);
	dfs(graph, i, j+1);
	dfs(graph, i, j-1);
	dfs(graph, i-1, j+1);
	dfs(graph, i+1, j-1);
	//换两种方向也一样 （发现不行） 
//	dfs(graph, i-1, j-1);
//	dfs(graph, i+1, j+1);
}

int main()
{
	int m, n;
	cin>>m>>n;
//	cout<<"m="<<m<<";n="<<n<<endl;
	vector<vector<char>> graph(m, vector<char>(n));
	char temp;
	for(int i=0; i<m; i++)
	{
		for(int j=0; j<n; j++)
		{
			cin>>temp;
			graph[i][j] = temp;
//			cout<<"temp="<<temp<<endl;
		}
	}
	int res = 0;
	for(int i=0; i<m; i++)
	{
		for(int j=0; j<n; j++)
		{
			if(graph[i][j] == 'C')
			{
				dfs(graph, i, j);
				res++; 
			}
		}
	}
	cout<<res<<endl;
	return 0;
}

/*
华为的机试题0714-2：这一题和leetcode上的1526一样 
题目： 
是给一组长度为N的整数字符串，每个箱子最终的位置，要求是把所有箱子都从0推到最终位置，允
许连续的箱子一起推，比如2，3，4号箱子都需要前进的话，推一次就可以，输出最少的推动次数。
输入： 
3 1 2 
输出：4 
if(nums[i] > nums[i-1])
	dp[i] = dp[i-1]+(nums[i]-nums[i-1]) 
else
	dp[i] = dp[i-1] 
dp[0] = nums[0]
*/ 
#include<bits/stdc++.h>
using namespace std;

int main()
{
	int a;
	vector<int> nums;
	while(cin>>a)
//	while(scanf("%d",&a)!=EOF)
	{
		nums.push_back(a);
	}
	vector<int> dp(nums.size(), 0);
	dp[0] = nums[0];
	for(int i=1; i<nums.size(); i++)
	{
		if(nums[i] > nums[i-1])
		{
			dp[i] = dp[i-1] + (nums[i] - nums[i-1]);
		}
		else
		{
			dp[i] = dp[i-1];
		}
	}
	cout<<dp[nums.size()-1]<<endl;
}

/*
华为的机试题0714-3：本题网上找不到输入输出测试样例，也不理解如何根据吞吐量构建图的边，希望厉害的大佬可以提供思路及相关代码 
 
题目： 网络维护：在一个n个结点的网络中，每个结点i的吞吐量为2^i，由于缺电(可能是湾湾)需要关闭其中的k个结点，
需要保证剩余结点仍能互通，输入就是n和k两个值，空格隔开，输出要求给出关闭的结点顺序，升序排列。n<100000好像是。
输入： 

输出： 

网上提供的一种做题思路，不过不是很理解 
先把顶点n加入res中，然后找到与res中顶点的距离小于等于n-k-len(res)的所有顶点中的最大值顶点x，
把x到res的路径上所有点加入res，
重复上述过程直到len(res)==n-k
*/ 
#include<bits/stdc++.h>