leetcode_day56

今日内容：

• 字符串接龙
• 有向图的完全可达性
• 岛屿的周长

字符串接龙

题目：

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

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

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

输入描述

第一行包含一个整数 N，表示字典 strList 中的字符串数量。 第二行包含两个字符串，用空格隔开，分别代表 beginStr 和 endStr。 后续 N 行，每行一个字符串，代表 strList 中的字符串。

输出描述

输出一个整数，代表从 beginStr 转换到 endStr 需要的最短转换序列中的字符串数量。如果不存在这样的转换序列，则输出 0。

思路：

注意：无向图搜索，最好用BFS

beginStr和endStr作为起始点，字典中的作为中间点，求最短路，即无向图求最短路。

但是这里并不是具体的点，而是字符串，路也需要判断

如果直接遍历所有字符串，根据差异直接建图，首先就会有\(O(n^2)\)的复杂度（还没算比较字符串差异的复杂度），然后还需要BFS，容易超时

carl利用字符串中只有小写字母的特点(题目并未提及只有小写字母，难以想到)，可以手动模拟所有的路，然后在已有的路中匹配，降低复杂度为常数26和在set、map中查找数据复杂度之积，代码如下：

for (int j = 0 ; j < 26; j++) {//遍历26个字母
    newWord[i] = j + 'a';
    if (newWord == endStr) { // 发现替换字母后，字符串与终点字符串相同
        cout <<  path + 1 << endl; // 找到了路径 
        return 0;
    }
    // 字符串集合里出现了newWord，并且newWord没有被访问过
    if (strSet.find(newWord) != strSet.end()
            && visitMap.find(newWord) == visitMap.end()) {
        // 添加访问信息，并将新字符串放到队列中
        visitMap.insert(pair<string, int>(newWord, path + 1));
        que.push(newWord);
    }
}

代码

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int N;
    cin >> N;
    string beginStr, endStr;
    cin >> beginStr >> endStr;
    unordered_set<string> set;
    string temp;
    for(int i = 0;i < N;i++) {
        cin >> temp;
        set.insert(temp);
    }
    queue<string> q;
    unordered_map<string, int> map;
    q.push(beginStr);
    map[beginStr] = 1;
    while(!q.empty()) {
        string word = q.front();
        q.pop();
        int path = map[word];
        for(int i = 0;i < word.size();i++) {
            for(int j = 0;j < 26;j++) {
                string newWord = word;
                newWord[i] = j + 'a';
 
                if(newWord == endStr) {
                    cout << path + 1;
                    return 0;
                }
                else {
                    if(set.find(newWord) != set.end() && map.find(newWord) == map.end()) {
                        map[newWord] = path + 1;
                        q.push(newWord);
                    }
                }
            }
        }
    }
 
    cout << 0 << endl;
    return 0;
}

有向图的完全可达性

题目：

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

输入描述

第一行包含两个正整数，表示节点数量 N 和边的数量 K。 后续 K 行，每行两个正整数 s 和 t，表示从 s 节点有一条边单向连接到 t 节点。

输出描述

如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。

思路：

不用传统dfs或bfs，既然是有向图可达，联想并查集路径压缩的思想，不断将路径压缩，随后如果还存在起点不是1号的路径，则输出-1。具体过程如下：

1. 统计所有直接与1相通的点，\(s[i]\)代表1号节点能否到达节点i
2. 其他边另成集，起点不断与s比较，若s[起点]=true，则删除这条边，同时更新s[终点]为true
3. 循环删除“其他边”，以冒泡排序思想检测本轮遍历是否有删除，若没有删除操作，则检查"其他边"，若仍存在，输出-1，若空，输出1

这种写法类似于BFS，每次只走一步。

代码

#include <bits/stdc++.h>
 
using namespace std;
//统计所有1出发的边，其他边另成集
//不断将其他边融合进1出发，如1，2  2，4 融合为1，4
//最后如果剩余有不可融合的边，则-1
//1出发边构建为s[101]表示从1到101的边是否存在
//其他边统计为vec<pair<int,int>> 如果起点与s重合则删除，并更新s
 
int main() {
    int N, K;
    cin >> N >> K;
    bool s[110] = {false};
    vector<pair<int, int>> edge;
    int a, b;
    for(int i = 0;i < K;i++) {
        cin >> a >> b;
        if(a == 1) s[b] = true;
        else edge.push_back({a, b});
    }
    bool changed = false;
    while(!edge.empty()) {
        for(int i = 0;i < edge.size();i++) {
            if(s[edge[i].first]) {
                s[edge[i].second] = true;
                swap(edge[i], edge[edge.size() - 1]);
                edge.pop_back();
                changed = true;
            }
        }
        if(changed == false && !edge.empty()) {
            cout << -1;
            return 0;
        }
        changed = false;
    }
    cout << 1;
    return 0;
}

岛屿的周长

题目：

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

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

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的周长。

思路：

由于地块都是方块，所以问题转化为小学生的数周长问题，公式为：

\(周长=块数*4-重合边数\)

那么可以统计块数和重合边数，最后求解答案即可。

也可以遍历所有地块，统计所有海岸长度。

还需注意岛屿问题的经典坑——全是陆地没有水。

代码

//每块四面，重合最少1最多4，遍历所有块计算每个的重合
#include <bits/stdc++.h>

using namespace std;


int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
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 ans = 0;
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < M;j++) {
            if(grid[i][j] == false) continue;
            for(int k = 0;k < 4;k++) {
                int x = i + dir[k][0];
                int y = j + dir[k][1];
                if(x < 0 || x >= N || y < 0 || y >= M || grid[x][y] == false) ans++;
            }
        }   
    }
    if(ans == 0) cout << 2*(N+M);
    else cout << ans;
    return 0;
}