百练-3723围棋

2023-11-03 03:40
文章标签 围棋 百练 3723

本文主要是介绍百练-3723围棋,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原文

描述围棋的棋盘上有19*19条线交织成的361个交点,黑棋和白棋可以下在交点上。我们称这些交点为“目”。

一个目的上下左右四个方向,称之为“气”,如果一个目的四个方向都被某一种颜色的棋子占据,那么即使这个目上并没有棋子,仍然认为这个目被该颜色棋子占据。

如下图中,四个黑棋中心的交点,由于被黑棋包围,因此我们认为这个目属于黑棋,

黑棋拥有4+1=5目


在棋盘的边框地区,只要占据目的三个方向,就可以拥有这个目。

黑棋拥有3+1=4目


同理在棋盘的四个角上,只要占据目的两个气即可。


黑棋拥有2+1=3目



推而广之,当有多个目互相连通的时候,如果能用一种颜色把所有交点的气都包裹住,那么就拥有所有目。

黑棋拥有6+2 = 8目


请编写一个程序,计算棋盘上黑棋和白棋的目数。
输入数据中保证所有的目,不是被黑棋包裹,就是被白棋包裹。不用考虑某些棋子按照围棋规则实际上是死的,以及互相吃(打劫),双活等情况。
输入第一行,只有一个整数N(1<=N<=100),代表棋盘的尺寸是N * N
第2~n+1行,每行n个字符,代表棋盘上的棋子颜色。

“.”代表一个没有棋子的目
“B”代表黑棋
“W”代表白棋

输出只有一行,包含用空格分隔的两个数字,第一个数是黑棋的目数,第二个数是白棋的目数。

样例输入
4
..BW
...B
....
....
样例输出
15 1
 
tips:这道题目的关键是通过什么策略找到额外获得‘目’,以黑棋为例,先找到一个黑子,然后搜索他四周所有可获得的目。
根据题设,不存在双杀等特殊情况,因此统计次连通分量所有的个数即可。

#include<iostream>  
#include<cstring>  using namespace std;  int n,cnt;  
int book[222][222];  
char mp[222][222];  
int dire[][2]={-1,0,1,0,0,-1,0,1};  
void dfs(int x,int y)  
{  for(int i=0;i<4;i++)  {  int nx=x+dire[i][0];  int ny=y+dire[i][1];  if(nx<1||nx>n||ny<1||ny>n)continue;  if(!book[nx][ny]&&mp[nx][ny]=='.'){  book[nx][ny]=1;  cnt++;  dfs(nx,ny);  }  }  
}  
int main()  
{  cin>>n;  for(int i=1;i<=n;i++)  {  for(int j=1;j<=n;j++)  {  cin>>mp[i][j];  }  }  for(int i=1;i<=n;i++)  {  for(int j=1;j<=n;j++)  {  if(!book[i][j]&&mp[i][j]=='B')  {  cnt++;  book[i][j]=1;  dfs(i,j);  }  }  }  cout<<cnt<<" "<<n*n-cnt<<endl;  return 0;  }   
PS:使用数组进行标记,dfs深搜;只算出黑色的,就可以得出白色的。并不需要完全包围 啊。

这篇关于百练-3723围棋的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/335338

相关文章

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

小火山 zzuli 1908 (围棋)

小火山的围棋梦想   Description 小火山最近喜欢上了围棋。 对于围棋,其实小火山是一窍不通的。现在棋盘上,有很多小火山的棋子。 如果棋盘上有这样的一个位置, 那么这个位置也会变成小火山 的棋子;这样的位置是指小火山的棋子将该位置围起来。 现在,小火山想知道实际棋盘是什么样子的。 你快来帮帮他吧! Input 输入第一行是一个整数T(T <= 30), 表示一

道路 Road(百练,POJ)

题目链接: 1724 -- ROADS (poj.org) 题目描述: 思路: 这题目乍一看,是一个含有2个标尺的单源最短路问题,挺难处理的。 既然没法直接用最短路处理,那我们就“记录信息”,将花费的时间也记录进dp数组,然后跑“状态最短路”。 用f[i][j] 表示到达点i 且 总花费时间为j的最短距离,然后跑堆优化的dijkstra算法就好。由于不含有负边权,因此可以搞一个vis数

Wireless Network(百练,POJ)

题目链接: http://bailian.openjudge.cn/tm2019/F/ 2236 -- Wireless Network 题面描述: 思路: 这题开了10s,所以可以暴力点,每次修复一个点,就将该点相连的那些边建出来,总的时间复杂度为: O(nm)。关键在于如何判定两个点是否是连通的。 刚开始我直接暴力DFS,发现T了,可能是用了DFS之后导致整个题的常数有点大。

百练--2746 -- 约瑟夫问题

2746:约瑟夫问题 总时间限制:  1000ms  内存限制:  65536kB 描述 约瑟夫问题:有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。 输入 每行是用空格分开

POJ 3723 Monthly Expense 二分

题意:给你n个值,要求将其划分成m部分(顺序不能打乱),如何划分使得最大部分的值最小。 题解:二分,对于每一个中间值,检测一次。 #include<cstdio>int N, M;int spend[200000];bool check ( int num ){int i, sum, cnt = 0;for ( i = 0; i < N; ){sum = 0; cnt++;w

围棋和五子棋分别从何时起源?它们的发展又是如何?

围棋和五子棋的起源一直以来就有很大的争议,虽然二者比较相似但不论是玩法还是精神内核上都有很大的区别,下面就就带大家了解围棋和五子棋的起源有哪些不同。 1.五子棋起源 五子棋最早可以追溯到中国古代的黑白棋,形式和围棋有诸多相似的地方,但核心玩法还是截然不同的。五子棋的起源虽然在中国,但在日本才真正得到了发展,根据日本史料记载中国古代的五子棋是先经由高丽(朝鲜),于1688年至1704年的日本元禄时

学习围棋,你最容易犯的十大错误!

围棋不管是在古代还是在现代都是品味和身份的象征,深受广大人民的喜爱,但围棋不像五子棋那么简单易学,相对五子棋来说,围棋玩法多变奥妙无穷。围棋高手对决都是眼观六路,耳听八方。稍有不甚就会满盘皆输。 下面几点是给初学者最容易犯的几点错误总结,希望对大家有帮助。      一、替人成空法:1、在对方棋形还不完整时,走出一些俗手、恶手,帮助对方把棋形补强,形成实空。(压四路、后推车等)      二、攻

四大围棋实战技巧

围棋之所以经久不衰,它的长生秘诀就在于“耐玩”,不过会玩的人不多,玩的精的就更少了。小编之前在亲朋围棋和棋友们下棋的时候就学到了四句有用的棋谚,感觉对围棋技艺的提升有很大的帮助,下面小编就为大家介绍一些围棋技巧,希望对大家有所帮助。 1.腾挪自靠始 围棋技巧之腾挪自靠始:腾挪,是指在敌强我弱的情况下,处理己方孤子的一种手段。应注意的是: 腾挪的一方是在逆境中作战,正面硬拼必然会遭受较大的损失,而

围棋360度谭

围棋360度谭 谭理事 360度 园周为什么是360度?这个是本来很简单的事情,让西方人编的什么古埃及人古苏美尔人的故事弄得一塌糊涂。要知道,古埃及人的故事在19世纪前鲜为人知,而古苏美尔人故事完全是西方人的科学考古的成果。其根本原因是西方人在19世纪战胜了中华帝国后,为了彻底和中华文明脱钩,不让这个老子管儿子的文化把自己管住,就从地下找到了这些文明成果。然后精心编造,最后以西方文明源于古