首页 > 编程语言 >图论篇--代码随想录算法训练营第五十三天打卡| 110. 字符串接龙,105.有向图的完全可达性,106. 岛屿的周长

图论篇--代码随想录算法训练营第五十三天打卡| 110. 字符串接龙,105.有向图的完全可达性,106. 岛屿的周长

时间:2024-09-08 18:21:44浏览次数:11  
标签:有向图 int 随想录 ++ vector grid visited include 可达性

110. 字符串接龙

题目链接:110. 字符串接龙

题目描述:

字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列: 

  1. 序列中第一个字符串是 beginStr。
  2. 序列中最后一个字符串是 endStr。 
  3. 每次转换只能改变一个字符。 
  4. 转换过程中的中间字符串必须是字典 strList 中的字符串,且strList里的每个字符串只用使用一次。 

给你两个字符串 beginStr 和 endStr 和一个字典 strList,找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列,返回 0。

解题思路:

这道题要解决两个问题:

  • 图中的线是如何连在一起的
  • 起点和终点的最短路径长度

1)判断点与点之间的关系,需要判断是不是差一个字符,如果差一个字符,那就是有链接

2)求起点和终点的最短路径长度,这里无向图求最短路,广搜最为合适,广搜只要搜到了终点,那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。

另外需要有一个注意点:

  • 本题是一个无向图,需要用标记位,标记着节点是否走过,否则就会死循环!
  • 使用set来检查字符串是否出现在字符串集合里更快一些

 

代码:

#include<iostream>
#include<unordered_set>
#include<queue>
#include<unordered_map>
#include<string>
using namespace std;

int main()
{
    int n;
    cin >> n;
    unordered_set<string> strList;
    string beginStr, endStr;
    cin >> beginStr >> endStr;
    for(int i = 0; i < n; i++) 
    {
        string s;
        cin >> s;
        strList.insert(s);
    }
    unordered_map<string,int> visitStr;
    queue<string> q;
    q.push(beginStr);
    visitStr.insert({beginStr,1});
    while(!q.empty())
    {
        string val = q.front();
        q.pop();
        int path = visitStr[val];
        for(int i = 0; i < val.size(); i++)
        {
            string newStr = val;
            for(int j = 0; j < 26; j++)
            {
                newStr[i] = j + 'a';
                if(newStr == endStr)
                {
                    cout << path + 1 << endl;
                    return 0;
                }
                if(visitStr.find(newStr) == visitStr.end() && strList.find(newStr) != strList.end())
                {
                    visitStr[newStr] = path + 1;
                    q.push(newStr);
                }
            }
        }
    }
    
    cout << 0 << endl;
    return 0;
}

105.有向图的完全可达性

题目链接:105. 有向图的完全可达性

题目描述:

给定一个有向图,包含 N 个节点,节点编号分别为 1,2,...,N。现从 1 号节点开始,如果可以从 1 号节点的边可以到达任何节点,则输出 1,否则输出 -1。

解题思路:

使用数组visited来保存当前节点的访问情况,使用dfs来遍历所有节点。最后如果所有节点均被访问,则输出1。

代码:

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;

void dfs(vector<list<int>>& graph,vector<bool>& visited,int key)
{
    if(visited[key]) return;
    visited[key] = true;
    for(auto x : graph[key])
        dfs(graph,visited,x);
}

int main()
{
    int n,k;
    cin >> n >> k;
    vector<list<int>> graph(n+1);
    for(int i = 0; i < k ; i++)
    {
        int s,t;
        cin >> s >> t;
        graph[s].push_back(t);
    }
    
    vector<bool> visited(n+1);
    dfs(graph,visited,1);
    for(int i = 1; i <= n; i++) 
        if(visited[i] == false) 
        {
            cout << -1 << endl;
            return 0;
        }
    cout << 1 << endl;
    return 0;
}

106. 岛屿的周长

题目链接:106. 岛屿的周长

题目描述:

给定一个由 1(陆地)和 0(水)组成的矩阵,岛屿是被水包围,并且通过水平方向或垂直方向上相邻的陆地连接而成的。

你可以假设矩阵外均被水包围。在矩阵中恰好拥有一个岛屿,假设组成岛屿的陆地边长都为 1,请计算岛屿的周长。岛屿内部没有水域。

解题思路:

1)找边法

遍历每一个空格,遇到岛屿则计算其上下左右的空格情况。如果该陆地上下左右的空格是有水域,则说明是一条边;如果该陆地上下左右的空格出界了,则说明是一条边;

2)公式法

结果 result = 岛屿数量 * 4 - cover * 2;

有一对相邻两个陆地,边的总数就要减2

每次只统计节点上边相邻陆地和其左边相邻陆地,其余方向不统计防止重复。

代码:

1)dfs找边法

#include<iostream>
#include<vector>
using namespace std;
 
int cnt = 0;
int dx[4] = {-1,0,0,1};
int dy[4] = {0,-1,1,0};
 
void dfs(vector<vector<int>>& grid,vector<vector<bool>>& visited,int r, int c)
{
    visited[r][c] = true;
    for(int i = 0 ; i < 4; i++)
    {
        int x = r + dx[i], y = c + dy[i];
        if(x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] == 0)
        {
            cnt++;
            continue;
        }
        if(grid[x][y] == 1 && !visited[x][y])
            dfs(grid,visited,x,y);
    }
}
 
int main()
{
    int n,m;
    cin >> n >> m;
    vector<vector<int>> grid(n,vector<int>(m));
    vector<vector<bool>> visited(n,vector<bool>(m));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> grid[i][j];
    for(int i = 0 ; i < n; i++)
        for(int j = 0; j < m; j++)
            if(grid[i][j] == 1 && !visited[i][j])
            {
                dfs(grid,visited,i,j);
                break;
            }
                 
    cout << cnt << endl;
    return 0;
}

2)直接找边法

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    int direction[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                for (int k = 0; k < 4; k++) {       // 上下左右四个方向
                    int x = i + direction[k][0];
                    int y = j + direction[k][1];    // 计算周边坐标x,y
                    if (x < 0                       // x在边界上
                            || x >= grid.size()     // x在边界上
                            || y < 0                // y在边界上
                            || y >= grid[0].size()  // y在边界上
                            || grid[x][y] == 0) {   // x,y位置是水域
                        result++;
                    }
                }
            }
        }
    }
    cout << result << endl;
 
}

3)公式法

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    int sum = 0;    // 陆地数量
    int cover = 0;  // 相邻数量
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                sum++; // 统计总的陆地数量
                // 统计上边相邻陆地
                if(i - 1 >= 0 && grid[i - 1][j] == 1) cover++;
                // 统计左边相邻陆地
                if(j - 1 >= 0 && grid[i][j - 1] == 1) cover++;
                // 为什么没统计下边和右边? 因为避免重复计算
            }
        }
    }

    cout << sum * 4 - cover * 2 << endl;

}

标签:有向图,int,随想录,++,vector,grid,visited,include,可达性
From: https://blog.csdn.net/m0_67804957/article/details/141998473

相关文章

  • 代码随想录算法训练营第九天 | Javascript | 力扣Leetcode | 手撕KMP的一天 | 28. 找
    目录前言简介题目链接:28.找出字符串中第一个匹配项的下标题目链接:459.重复的子字符串前言踏平坎坷成大道,斗罢艰险又出发!自律的尽头是自控,自控的尽头是硬控。愿道友们披荆斩棘,终能得偿所愿。简介本人是小几年经验的前端开发,算法基础只有力扣几十道题,非常薄弱。......
  • 【代码随想录Day10】栈与队列Part01
    232.用栈实现队列题目链接/文章讲解/视频讲解:用栈实现队列classMyQueue{Stack<Integer>stackIn;Stack<Integer>stackOut;publicMyQueue(){stackIn=newStack<>();stackOut=newStack<>();}publicvoidpush(int......
  • 【代码随想录Day9】字符串Part02
    151.翻转字符串里的单词解题思路如下:移除多余空格将整个字符串反转将每个单词反转举个例子,源字符串为:"theskyisblue"移除多余空格:"theskyisblue"字符串反转:"eulbsiykseht"单词反转:"blueisskythe"题目链接/文章讲解/视频讲解:代码随想录publicclassS......
  • 代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II
    代码随想录刷题day25丨491.递增子序列,46.全排列,47.全排列II1.题目1.1递增子序列题目链接:491.非递减子序列-力扣(LeetCode)视频讲解:回溯算法精讲,树层去重与树枝去重|LeetCode:491.递增子序列_哔哩哔哩_bilibili文档讲解:https://programmercarl.com/0491.%E9%80......
  • 代码随想录day 53 || 图论4
    字符串接龙varqueue*list.ListvarvisitMapmap[string]boolfuncmain(){ varcountint fmt.Scanf("%d",&count) varstartStr,endStrstring fmt.Scanf("%s%s",&startStr,&endStr) varstrList=make([]string,count) fo......
  • 代码随想录算法训练营第五十天 | 98. 所有可达路径
    目录98.所有可达路径思路图的存储邻接矩阵         邻接表深度优先搜索1.确认递归函数,参数2.确认终止条件3.处理目前搜索节点出发的路径方法一:邻接矩阵写法方法二:邻接表写法98.所有可达路径题目链接:卡码网题目链接(ACM模式)文章讲解:代码随想录 ......
  • 信息学奥赛初赛天天练-84-NOIP2014普及组-基础题3-总线、存储器、邮件协议、二叉树、
    信息学奥赛初赛天天练-84-NOIP2014普及组-基础题3-总线、存储器、邮件协议、二叉树、满二叉树、顶点的度、无向图、有向图PDF文档公众号回复关键字:202409061NOIP2014普及组基础题36CPU、存储器、I/O设备是通过()连接起来的A接口B总线C控制线D系统文......
  • 代码随想录算法训练营第十天| 232.用栈实现队列 、 225. 用队列实现栈 、20. 有效的括
    学习文章链接:代码随想录文章目录一、232.用栈实现队列二、225.用队列实现栈三、20.有效的括号四、1047.删除字符串中的所有相邻重复项一、232.用栈实现队列题目链接:232.用栈实现队列栈的操作:stack<int>s;s.empty();//如果栈为空则返回true,......
  • 代码随想录day52 || 图论3
    岛屿最大的孤岛面积packagemainimport"fmt"vardirPath=[4][2]int{{0,-1},{1,0},{0,1},{-1,0}}varvisited[][]boolvarflagboolvarresintfuncmain(){ varx,yint fmt.Scanf("%d%d",&x,&y) //x行y列初始化临界矩阵 vargra......
  • 【代码随想录训练营第42期 Day51打卡 - 岛屿问题 - 卡码网 99. 岛屿数量 100. 岛屿的
    目录一、做题心得二、题目与题解题目一:99.岛屿数量题目链接题解1:DFS 题解2:BFS 题目二:100.岛屿的最大面积题目链接题解:DFS 三、小结一、做题心得今天打卡的是经典的岛屿问题:分别从两个方向进行探讨--深搜(DFS)与广搜(BFS)。作为这两大基本搜索最经典的例题,今天......