dfs 三子棋 30分求条
  • 板块灌水区
  • 楼主Xy110319
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/10/15 17:37
  • 上次更新2024/10/15 20:06:02
查看原帖
dfs 三子棋 30分求条
1071571
Xy110319楼主2024/10/15 17:37

题目描述 33DAI 很喜欢三子棋。今天他在一张很大的方形棋盘上下棋,棋盘可以看作是一个 行 列的网格。(大家应该知道三子棋是下在格子里面的吧?)

33DAI 今天的玩法非常不一样。棋盘上有些位置上有棋子,有些位置上没有。所有的棋子都是己方棋子。33DAI 可以任选一个空着的位置下棋。如果他落子的位置能和周边的另外两个棋子构成三连(横着、竖着、斜着都可以),那么这就是一个好位置。

请你帮 33DAI 找找棋盘上有多少个好位置吧!

输入格式 第一行为空格隔开的两整数 ,。

接下来 行,每行为 个字符,描述了整个棋盘,第 行第 列的字符为 ,描述了第 行第 列的格子。

如果字符为 . 则表示这个位置没有棋子,如果字符为 # 则表示这个位置有一个己方棋子。

输出格式 一行一个整数,表示有多少个空着的位置是好位置。

5 7

.......

...#...

...##..

.......

...#..#

6 样例解释 下面用字符 o 标出了所有好位置

..oo...

...#...

..o##o.

...o.o.

...#..#

#include<bits/stdc++.h>
using namespace std;
long long cnt,n,m,dx[8]={-1,1,0,0,-1,1,-1,1},dy[8]={0,0,-1,1,-1,1,1,-1};
char a[100][100];
long long dfs(long long x,long long y){
	for(long long i=0;i<=7;i++){
		if(x-dx[i]>n||y-dy[i]>m||x+dx[i]>n||y+dy[i]>m||x-dx[i]<1||y-dy[i]<1||x+dx[i]<1||y+dy[i]<1){
			continue;
		}
		if(a[x+dx[i]][y+dy[i]]=='#'){
			a[x-dx[i]][y-dy[i]]='/';
		}
	}
	return 0;
}
signed main(){
	cin>>n>>m;
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			if(a[i][j]=='#'){
				dfs(i,j);
			}
		}
	}
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			if(a[i][j]=='/'){
				cnt++;
			}
		}
	}
	cout<<cnt;
	return 0;
}
2024/10/15 17:37
加载中...