首页 > 其他分享 >SP2128题解

SP2128题解

时间:2022-09-19 21:55:37浏览次数:103  
标签:判断 格子 题解 矩阵 gg 左上方 mp SP2128

题意

共有 \(t\) 个 \(n \times m\) 的由 .xo 组成的字符矩阵。设矩阵中连续 \(k\) 格为 x 小 A 加一分,连续 \(k\) 格为 o 小 B 加一分。

正文

\(\Large{时间复杂度:}\large\mathcal{O}(tnmk)\)

\(\Large{算法:暴力}\)

此题我第一眼看就知道很水(尽管我调试了半天)。

遍历矩阵,对于每格,进行 8 次判断。每次向一个方向连续移动 \(k-1\) 格,每次判断移到的格子是否与原格子相同,若不同,终止此次判断。

例子:在 \((5,5)\) 向左上方向检查,判断是否有 5 子相连。

1 2 3 4 5
1 x
2
3 x
4 x
5 x

向左上方向移动一格到 \((4,4)\),读取 \((4,4)\) 的值为 x,与原格子 \((5,5)\) 的值相同,继续判断;再向左上方移动一格到 \((3,3)\),读取 \((3,3)\) 的值为 x,与原格子的值相同,继续判断;移到 \((2,2)\),发现 \((2,2)\) 的值与原格子不符,表明例子条件下并没有 5 子相连。

连续遍历直至找到符合的格子,进行加分,若整个矩阵没有符合条件的格子,则判断平局。

上代码:

#include<bits/stdc++.h>
using namespace std;
using gg=long long;
gg t;
gg n,m,k;
gg mp[1000][1000];//储存矩阵
gg pts[3];
gg q;
bool f(gg x,gg y,gg x_,gg y_,gg k){//之前看一位大佬用了较多个dfs,感觉有点麻烦,x_和y_控制判断的方向
	q=mp[x][y];//读取原格子的值
	if(q==0){
		return false;
	}
	for(gg i=1;i<k;i++){
		if(x+x_*(k-1)>=0 && x+x_*(k-1)<=n && y+y_*(k-1)>=0 && y+y_*(k-1)<=m){//判断是否会越界
			if(mp[x+x_*i][y+y_*i]!=q){
				return false;
			}
		}
		else{
			return false;
		}
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>t;
	for(gg i=1;i<=t;i++){
		cin>>m>>n>>k;
		memset(mp,0,sizeof mp);//初始化
		for(gg j=1;j<=n;j++){
			for(gg l=1;l<=m;l++){
				char c;
				cin>>c;
				mp[j][l]=(c=='.'?0:(c=='x'?1:2));//将字符转换成整形值输入,方便
			}
		}
		for(gg j=1;j<=n;j++){
			for(gg l=1;l<=m;l++){
				if(f(j,l,1,0,k) || f(j,l,1,1,k) || f(j,l,0,1,k) || f(j,l,-1,0,k) || 
				f(j,l,0,-1,k) || f(j,l,-1,-1,k) || f(j,l,1,-1,k) || f(j,l,-1,1,k)){//连续判断
					pts[q]++;
					goto end_;//一些厌恶goto的轻喷,但不得不说真的方便
				}
			}
		}
		end_: ;
	}
	cout<<pts[1]<<':'<<pts[2];
	return 0;//虽然代码看着有点长,但本蒟蒻觉得是比较好理解的吧
}

提交记录,华丽结束。

后附

日志

v1.9 on 2022.9.3: 改正

标签:判断,格子,题解,矩阵,gg,左上方,mp,SP2128
From: https://www.cnblogs.com/wanguan/p/16694709.html

相关文章

  • 【Coel.解题报告】【没事找事】CSP-S2 真题解析
    昨天刚考完CSP-S1,反正没什么想做的(最近好颓废…),来复盘一下。本次比赛评价(转载):CSP-S1是由CCF自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「基数排序......
  • 牛客题解 珂朵莉与宇宙
    链接:https://ac.nowcoder.com/acm/problem/14600来源:牛客网题解作者岛田小雅这道题很仁慈地直接告诉了我们子区间的个数,如果直接暴力遍历所有的子区间,复杂度是\(O(\f......
  • PostgreSQL常见问题解决
    psql找不到动态链接库 2022-09-19 psql:symbollookuperror:psql:undefinedsymbol:PQsetErrorContextVisibility      解决办法:  找到PG......
  • 第十四章 Redis应用问题解决
    一、缓存穿透1.问题描述key对应的数据在数据源并不存在,每次针对此key的请求从缓存获取不到,请求都会压到数据源,从而可能压垮数据源。比如用一个不存在的用户id获取用户信......
  • 牛客题解 武藏牌牛奶促销
    链接:https://ac.nowcoder.com/acm/problem/13592来源:牛客网题解作者岛田小雅看到这一题我第一反应想直接模拟,看了下范围感觉可行,但是如果遇到无法判断的INF就会导致......
  • P1559 运动员最佳匹配问题 题解
    本篇使用\(\text{KM}\)算法求解。对于\(\text{KM}\)算法步骤如下:首先要用邻接矩阵存二分图,然后用贪心算法初始化标杆,运用匈牙利算法找到完美匹配,如果找不到则修改标......
  • SWERC 2021-2022 部分简要题解
    比赛链接:https://codeforc.es/contest/1662。前言「部分」「简要」题解。A-OrganizingSWERC直接判断。C-EuropeanTrip如果不考虑限制,我们可以直接矩乘。考虑......
  • 【题解】CF1311E Construct the Binary Tree
    题目链接-->Problem-E-Codeforces题目大意给定\(n\)和\(d\),你需要构造一棵\(n\)个点的二叉树满足所有点的深度之和恰好为\(d\)。\(2≤n,d≤5000\)。分析......
  • CSP2021-s题解
    T1廊桥分配题目链接P7913[CSP-S2021]廊桥分配\(Lemma:\)对于已经存在的廊桥集合,加入新的廊桥不会影响之前分配好的航班。证明:由于题目所给限制,若有空廊桥,则航......
  • Luogu P3674 小清新人渣的本愿 题解
    P3674小清新人渣的本愿lxl大爷的题,%%%%%以及CSPrp++!!!前言:其实是这题的名字吸引了我,毕竟人渣的本愿里的角色我觉得多多少少都沾点,哪来的小清新啊。《人渣的本愿》,又名......