首页 > 墨奇科技18号笔试
头像
没有我进不了的人才库-
发布于 2021-07-18 16:32
+ 关注

墨奇科技18号笔试

老哥们,第二题我统计好上下左右的1的个数,然后再求L的数量,通过率0%,我就用的暴力,哪里错了吗?测试案例通过

测试案例:
2
4 3
1 0 0
1 0 1
1 0 0
1 1 0
6 4
1 0 0 0
1 0 0 1
1 1 1 1
1 0 1 0
1 0 1 0
1 1 1 0
    
答案:
Case #1: 1
Case #2: 9


int fn(int x, int y)//这里的x,y是不包含data[i][j]的,所以后面的min_num和max_num都+1
{
	int min_num = min(x, y);
	int max_num = max(x, y);
	int val = 0;
	if (x != 0 && y != 0)
	{
        //min_num中从2开始,有多少个L形
		for (int k = 2; k <= min_num + 1; k++) {
			if (k * 2 <= max_num+1)val++;
			else break;
		}
        //上一个for中,max_num的值最小会从4开始(k*2=4),所以max_num的段
        //还可以从2或者3开始
		if (min_num + 1 >= 6)val += 2;//因为min_num+1>=6,所以max_num可以为2或3
		else if (min_num + 1 >= 4)val += 1;//max_num可以为2
		return val;
	}
	return 0;
}
int cal_num(vector<vector<int>>&data)
{
	int m = data.size();
	int n = data[0].size();
	int num = 0;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (data[i][j] == 0)continue;
			int r_left = 0, r_right = 0;
			int c_up = 0, c_down = 0;
            //点data[i][j]左边的连续1的个数(不包括data[i][j])
			for (int k = j - 1; k >= 0; k--)
				if (data[i][k] == 1)r_left++;
				else break;
            //点data[i][j]右边的连续1的个数(不包括data[i][j])
			for (int k = j + 1; k < n; k++)
				if (data[i][k] == 1)r_right++;
				else break;
            //点data[i][j]上边的连续1的个数(不包括data[i][j])
			for (int k = i - 1; k >= 0; k--)
				if (data[k][j] == 1)c_up++;
				else break;
            //点data[i][j]下边的连续1的个数(不包括data[i][j])
			for (int k = i + 1; k < m; k++)
				if (data[k][j] == 1)c_down++;
				else break;
            
            //计算L形的数量
			num += fn(c_up, r_left);
			num += fn(c_up, r_right);
			num += fn(c_down, r_left);
			num += fn(c_down, r_right);
		}
	}
	return num;
}
int main()
{
	int T = 0;
	cin >> T;
	int r = 0, c = 0;
	for (int i = 0; i < T; i++)
	{
		cin >> r >> c;
		vector<vector<int>>data(r, vector<int>(c, 0));
		for (int x = 0; x < r; x++)
		{
			for (int y = 0; y < c; y++)
			{
				cin >> data[x][y];
			}
		}
		cout << "Case #" << i + 1 << ": " << cal_num(data) << endl;
	}
	system("pause");
	return 0;
}


全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐