首页 > 其他分享 >1113. 红与黑

1113. 红与黑

时间:2023-05-08 17:57:27浏览次数:51  
标签:cnt ny int 红与黑 dfs nx vis 1113

题目描述

地砖有红和黑两种颜色,站在给定的某个黑色地砖上,问有多少块黑色地砖可达?

f1 dfs计算连通性

基本分析

  1. dfs返回什么?从当前节点出发可达的黑色地砖个数
  2. dfs怎么实现?
    • 初始化cnt;
    • 修改vis状态;
    • 枚举可选的4相邻地砖(越界跳过,访问过跳过,红色跳过,累加下一步可达的个数)
    • 返回cnt

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 25;

int m, n;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
bool vis[N][N];
char g[N][N];


int dfs(int x, int y)
{
    int cnt = 1;
    
    vis[x][y] = true;
    
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (g[nx][ny] == '#') continue;
        if ( nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (vis[nx][ny]) continue;
        cnt += dfs(nx, ny);
    }
    
    return cnt;
}

int main()
{
    while (cin >> m >> n, m || n)
    {
        for (int i = 0; i < n; i++) cin >> g[i];
        
        int x, y;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == '@')
                    x = i, y = j;
                    
        memset(vis, 0, sizeof vis);
        cout << dfs(x, y) << endl;
    }
    
    return 0;
}

总结

  1. 这里n和m不同,怎么定义g和vis?直接给一个大的N
  2. 这里m和n的含义?m是横向,n是纵向。放到坐标中向右是y,向下是x
  3. 不能忘记初始化vis数组

标签:cnt,ny,int,红与黑,dfs,nx,vis,1113
From: https://www.cnblogs.com/zk-icewall/p/17382485.html

相关文章

  • INFO1113 / COMP9003
    INFO1113/COMP9003AssignmentDue:14May2023,11:59PMAESTThisassignmentisworth18%ofyourfinalgrade.TaskDescriptionInthisassignment,youwillcreateagameintheJavaprogramminglanguageusingtheProcessinglibraryforgraphicsandgradleas......
  • 红与黑
    铀是一道水题有一个矩形房间,覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上,由此出发,可以移到四个相邻瓷砖之一,但他不能移动到红砖上,只能移动到黑砖上。编写一个程序,计算他通过重复上述移动所能经过的黑砖数(站立的黑砖也要算)。输入开头行包含两个正整......
  • Eigensequence UVA - 11133
    给你一个递增序列的第一位a1,最后一位an,求有多少个序列满足:以a1为首,an为尾 1、B(1)=A(1)2、后面每项满足A[j]=B[j], A(j-1)<B(j)≤A(j),且bj能整除A(j)-A(j-1)。   F[i][j]最后一位为j的方案数#include<iostream>#include<cstring>#include<a......
  • 红与黑
    有一个矩形房间,覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上,由此出发,可以移到四个相邻瓷砖之一,但他不能移动到红砖上,只能移动到黑砖上。编写一个程序,计算他通过重复上述移动所能经过的黑砖数(一开始站立的黑砖也要算)。输入开头行包含两个正整数W和H,W和H......
  • NFO1113 / COMP9003
    INFO1113/COMP9003AssignmentDue:14May2023,11:59PMAESTThisassignmentisworth18%ofyourfinalgrade.TaskDescriptionInthisassignment,youwillcreateagameintheJavaprogramminglanguageusingtheProcessinglibraryforgraphicsandgradle......
  • 力扣1113(MySQL)-报告的记录(简单)
    题目:动作表:Actions 此表没有主键,所以可能会有重复的行。action字段是ENUM类型的,包含:('view','like','reaction','comment','report','share')extra字段是可选的信息(可能为null),其中的信息例如有:1.报告理由(areasonforreport)2.反应类型(atypeo......
  • 11113344
    世界上没有一个静止不动的时刻,技术也在不断地变化,那么,作为开发者和博主,我们如何才能跟上时代的步伐?答案很简单,就是不被定义,不受限制,勇于追求自己想要成为的样子。人生当中,我......
  • 数据库在执行全库恢复后,open时报错ORA-01113、ORA-01110 ORA-00312 ORA-01113
    问题描述:数据库在执行全库恢复后,open时报错ORA-01113、ORA-01110ORA-00312ORA-01113系统:Anolis7.9数据库:oracle11.2.0.41、问题描述数据库在执行全库恢复后,open时报错OR......
  • 洛谷 P1113 杂务(拓扑排序,递归)
    题目大意:有一个有向无圈图,每个节点看作一个任务,一个任务需要完成必须先完成父亲节点的任务,每个任务都有耗时。假设现在所有不相关任务都可以并行执行,问最短多少时间可以把所......
  • F2F-L8U3-Describing our job skills 20221113
    Areyoureadyforyourdreamjob?Findthewordsorphraseswiththemeaningsbelow.ffAvailableJOBS......