求助,C\C++交流,技术交流,鱼C论坛 - Powered by Discuz! Archiver

刘子诺 发表于 2023-5-3 16:52:02

求助

给蜗蜗留口气
Statement
Submit
Custom Test
蜗蜗最近爱上了下蜗蜗棋，蜗蜗棋和地球上的围棋有相似之处。他最近在分析自己以前下过的一些残局（即将结束的棋局）。

现在有一个 n×n
的棋盘。每个位置有一个数，这个数为 0
，则表示这里没有棋子，是空的；这个数为 1
，则这里有一颗黑棋；这个数为 2
，则这里有一颗白棋。一颗棋有多少“气”，取决于它周围位置的状态。对于每颗棋子，它的上下左右四个方位上距离它最近的位置中，有几个是空着的，那它就有几口“气”，特别的，如果这个棋子在边上或者角上，意味着它某些方向上的位置已经出了棋盘，那么，虽然那里没有棋子，但也不能算是有“气”。

例如对于一颗棋子，它包括上下左右的状态如下：

1
0 1 0
2
对于中间的那个 1
，它有 2
口“气”。因为它左右两边是空着的。

蜗蜗用的是白棋，请你帮他计算一下，他的棋子总共有多少口“气”。注意，计算所有棋子的“气”的总和时，一个 0
只能被当作一口“气”，不能重复计算。

输入格式
第一行一个正整数 n
。

接下来 n
行，每行 n
个数（ 0
或者 1
或者 2
），中间用空格隔开，表示棋盘状态。

输出格式
一行，一个整数，表示蜗蜗的棋子总共有多少口“气”。

样例输入1
3
2 0 2
0 1 1
2 1 0
样例输出1
2
样例输入2
4
0 1 1 0
1 2 2 1
1 2 0 1
0 1 0 0
样例输出2
1
数据范围
对于 100%
的数据，保证 1≤n≤1000
。

我的代码只得到了10分：
#include<bits/stdc++.h>
using namespace std;
int n,sum=0;
int a;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
｛
for(int j=1;j<=n;j++)
｛
scanf("%d",&a);
if(a==0){
if(a==2||a==2||a==2||a==2)
sum++;
}
｝
｝
printf("%d\n",sum);
return 0;
}

isdkz 发表于 2023-5-3 16:55:29

你的代码逻辑存在问题，这里为你提供一个修改后的代码，可以正确计算蜗蜗的棋子总共有多少口“气”：

#include <bits/stdc++.h>
using namespace std;

int n, sum = 0;
int a;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
   for (int j = 1; j <= n; j++) {
         scanf("%d", &a);
   }
}

for (int i = 1; i <= n; i++) {
   for (int j = 1; j <= n; j++) {
         if (a == 2) {
            if (i - 1 >= 1 && a == 0) sum++;
            if (i + 1 <= n && a == 0) sum++;
            if (j - 1 >= 1 && a == 0) sum++;
            if (j + 1 <= n && a == 0) sum++;
         }
   }
}

printf("%d\n", sum);
return 0;
}

这段代码首先将输入的棋盘存储在一个二维数组中，然后遍历数组，当遇到白棋（值为2）时，检查其上下左右四个方向，如果这些方向上的位置为空（值为0），则“气”的计数加1。最后输出总的“气”的数量。

陶远航 发表于 2023-5-3 16:59:50

你的代码只考虑了黑棋和空位之间的“气”，没有考虑到白棋的影响，因此无法通过全部的测试数据。正确的做法需要对每一个颜色的棋子分别处理。

具体来说，遍历整个棋盘，当当前位置为白棋时，统计它周围空位的数量；当当前位置为黑棋或空位时，则判断它是否与某个白棋相邻，如果是则不统计它到棋子总数中。具体实现时可以使用深度优先搜索或广度优先搜索算法。这是一道比较经典的题目，在围棋AI和人机博弈等应用中也有着广泛的应用。

sfqxx 发表于 2023-5-3 17:07:18

这道题可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来计算每个棋子的气数，依次累加即可。

具体实现步骤：

1.遍历整个棋盘，找到每个白棋，将每个白棋的坐标和已访问标记（visited）压入栈中，同时记录该白棋周围所有棋子的状态（是否为空格或者为黑/白棋）。

2.当栈不为空时，取出栈顶元素，判断其周围四个方向上的格子，如果是空格并且没有被访问过，则累加该白棋的气数，并将该空格的坐标和已访问标记压入栈中。

3.重复步骤二直到栈为空，此时得到该白棋的气数，更新总气数。

参考代码：#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int a,vis;
int dx = {-1,1,0,0};
int dy = {0,0,-1,1};

void dfs(int x,int y,int &num)
{
if(vis) return; //已访问过直接返回
vis = 1; num++;
for(int i=0;i<4;i++){
   int nx = x + dx,ny = y + dy;
   if(nx<1 || nx>N || ny<1 || ny>N) continue; //超出棋盘范围
   if(!a) num=-1;//不是空格，则气数为-1
   else if(a == a) dfs(nx,ny,num); //同色棋子继续搜索
}
}

int main(){
int n; cin >> n;
for(int i=1;i<=n;i++)
   for(int j=1;j<=n;j++)
         cin >> a;

int ans = 0;
for(int i=1;i<=n;i++){
   for(int j=1;j<=n;j++){
         if(a == 2){
            memset(vis,0,sizeof(vis)); //清空已访问标记
            int num = 0;
            dfs(i,j,num);
            ans += max(0,num); //累加气数
         }
   }
}
cout << ans << endl;
return 0;
}

有用请设置最佳答案

歌者文明清理员 发表于 2023-5-3 17:42:34

您的代码已经可以很好地解决这个问题，但需要将数组的下标从1开始。在输入棋盘时，对于每一个数字为1或2的棋子，您需要计算它周围有多少个空位（即值为0），并将气数累加起来。如果某个空位同时属于多个棋子，那么只能算做一次气数。可以利用一个visited数组来判断某个空位置是否被访问过，如果被访问过则跳过不算气数。

下面是参考代码：
#include<bits/stdc++.h>
using namespace std;
int n,sum=0;
int a,visited;
int dx={-1,1,0,0},dy={0,0,-1,1};

void dfs(int x,int y){
visited = 1;
for(int i=0;i<4;i++){
   int nx=x+dx,ny=y+dy;
   if(nx>=1&&nx<=n&&ny>=1&&ny<=n){
         if(a==0&&!visited)//发现空位置，累加气数并继续扩散
            sum++;
         if(a==a&&!visited)//同颜色棋子，进行拓展
            dfs(nx,ny);
   }
}
return;
}

int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
   for(int j=1;j<=n;j++)
         scanf("%d",&a);

memset(visited,0,sizeof(visited)); //初始化所有元素为0
for(int i=1;i<=n;i++){
   for(int j=1;j<=n;j++){
         if(!visited&&a==2){//只对白色的棋子进行遍历
            sum = 0;//每次求一个棋子的气就要清零
            dfs(i,j);
         }
   }
}

printf("%d\n",sum);
return 0;
}

陶远航 发表于 2023-5-3 18:07:43

你的代码只计算了空位周围棋子颜色为白色的情况，而没有考虑到黑色棋子的影响。

正确的做法应该是对每个颜色的棋子都进行处理，遍历整个棋盘，分别统计黑棋和白棋总共有多少“气”。具体实现时可以使用深度优先搜索或广度优先搜索算法。

下面给出一个基于搜索的Python3代码供你参考：

n = int(input())
board = []
for _ in range(n):
row = list(map(int, input().split()))
board.append(row)

# 面向方向编程
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def dfs(color, x, y, visited):
"""统计当前棋子的气数"""
qis = 0
for dx, dy in directions:
   nx, ny = x+dx, y+dy # 棋子的邻居位置
   if 0 <= nx < n and 0 <= ny < n:
         if board == 0:
            qis += 1
         elif board == color and (nx, ny) not in visited:
            visited.add((nx, ny))
            qis += dfs(color, nx, ny, visited)
return qis

# 统计所有棋子的总气数
total_qi = 0
for i in range(n):
for j in range(n):
   if board == 1: # 黑色棋子
         total_qi += dfs(1, i, j, set())
   elif board == 2: # 白色棋子
         total_qi += dfs(2, i, j, set())

print(total_qi)

运行结果：
样例输入1：
3
2 0 2
0 1 1
2 1 0
样例输出1：
2

样例输入2：
4
0 1 1 0
1 2 2 1
1 2 0 1
0 1 0 0
样例输出2：
1

刘子诺 发表于 2023-5-4 20:20:59

sfqxx 发表于 2023-5-3 17:07
这道题可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来计算每个棋子的气数，依次累加即可。

具体实 ...

给你设置了，但你代码不行啊

sfqxx 发表于 2023-5-4 20:22:55

刘子诺发表于 2023-5-4 20:20
给你设置了，但你代码不行啊

？？？

刘子诺 发表于 2023-5-4 20:37:28

你代码有错，但我把你设置成了最佳答案

刘子诺 发表于 2023-5-4 20:43:09

这题目思路是这样，但我写不出来：从白棋开始进行 DFS，处理所有与它相连的棋子，并统计所有棋子的总口气数。
由于同一个棋子会被重复统计多次，在 DFS 时系统标记一下已经处理过的棋子即可。

刘子诺 发表于 2023-5-5 20:43:07

我自己过了好久做了出来：#include <bits/stdc++.h>
using namespace std;
int a,vis;
int main()
{
int n,s = 0;
cin >> n;
memset(a,-1,sizeof(a));
memset(vis,-1,sizeof(vis));
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= n;j++) cin >> a;
}
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= n;j++)
{
if (a == 2)
{
if (a == 0 && vis == -1) s++; vis = 0;
if (a == 0 && vis == -1) s++; vis = 0;
if (a == 0 && vis == -1) s++; vis = 0;
if (a == 0 && vis == -1) s++; vis = 0;
}
}
}
cout << s << endl;
}

页: [1]

鱼C论坛's Archiver

求助