[Luogu]SP2128题解
2022/9/14 23:19:04
本文主要是介绍[Luogu]SP2128题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
[Luogu]SP2128 KROW
题意
共有 \(t\) 个 \(n \times m\) 的由 .
、x
、o
组成的字符矩阵。设矩阵中连续 \(k\) 格为 x
小 A 加一分,连续 \(k\) 格为 o
小 B 加一分。
正文
最坏时间复杂度:\(\mathcal{O}(tnmk)\)
算法:暴力
此题我第一眼看就知道很水(尽管我调试了半天)。
遍历矩阵,对于每格,进行 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: 改正
这篇关于[Luogu]SP2128题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行
- 2024-05-08阿里云域名注册流程,分享给第一次购买域名的新手站长!