提交好几次dfs总算过了,对vis数组做了点处理
  • 板块P1141 01迷宫
  • 楼主Tz1934
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/3/13 16:19
  • 上次更新2024/3/13 17:08:31
查看原帖
提交好几次dfs总算过了,对vis数组做了点处理
1308683
Tz1934楼主2024/3/13 16:19

所有连通的不同的区域用不同的mark标记,即访问与否不用1和0来区别 代码如下

int dfs(int x, int y,int mark)
{
	int sum = 1;
		for (int k = 0; k < 4; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx >=0 && ny >= 0 && nx < n && ny < n&&a[nx][ny]!=a[x][y] && !vis[nx][ny])
			{
				vis[nx][ny] = mark;
				sum+=dfs(nx, ny,mark);
			}

		}
	return sum;
}
while(i<m)
{
	int nx;
	int ny;
	scanf_s("%d%d", &nx, &ny);
	if (!vis[nx-1][ny-1])
	{
		vis[nx-1][ny-1] = i+1;
		result[i] = dfs(nx - 1, ny - 1,i+1);//用i加1进行标记
		i++;
	}
	else//若已被标记,用标记值的下标索引即可
	{
		result[i] = result[vis[nx-1][ny-1]-1];
		i++;
	}
}  
2024/3/13 16:19
加载中...