算法训练（leetcode）第四十六天 | 110. 字符串接龙、105. 有向图的完全可达性、106. 岛屿的周长

*110. 字符串接龙

题目地址

使用广搜。
本题相当于求最短路径，因此使用广搜。如何应用广搜是一个难点，因为题目给的是字符串而非图的表示（邻接矩阵、邻接表），因此需要自行构建连接关系。

题目要求每一步只能修改一个字符，因此从起始字符串开始，对字符串中的每一个字符进行修改，修改后在输入的字符串列表中查找是否存在，若存在则放入队列中用于广搜同时记录步数+1。若修改后的字符串等于结束字符，则直接输出当前步数+1.

使用广搜时，搜索的每一圈内的字符串所记录的步数是一致的。

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

// c++
#include<bits/stdc++.h>
using namespace std;int main(){string beginStr, endStr, str;int n;unordered_set<string> strSet;cin>>n;cin>>beginStr>>endStr;for(int i=0; i<n; i++){cin>>str;strSet.insert(str);}// 记录访问过的路径以及路径长度unordered_map<string, int> visitMap;visitMap.insert({beginStr, 1});// BFSqueue<string> que;que.push(beginStr);while(!que.empty()){string word = que.front();que.pop();int path = visitMap[word];// cout<<"word: "<<word<<endl;// 更换单词里的一个字符for(int i=0; i<word.size(); i++){string newWord = word;// cout<<"newWord: "<<newWord<<endl;for(int j=0; j<26; j++){newWord[i] = j + 'a';// 可以到达结束字符则直接结束输出if(newWord == endStr){cout<<path+1<<endl;return 0;}if(strSet.find(newWord)!=strSet.end() && visitMap.find(newWord) == visitMap.end()){// visitMap[word] = path + 1;// 存入路径记录里visitMap.insert({newWord, path + 1});// 入队 BFSque.push(newWord);// cout<<newWord<<endl;}}}}cout<<0<<endl;return 0;
}

105. 有向图的完全可达性

leetcode题目地址

使用深度优先遍历，探查是否能够到达每个结点。

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

邻接矩阵

// c++
#include<bits/stdc++.h>
using namespace std;
int direction[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
void dfs(const vector<vector<int>> &matrix,vector<bool> &result,int x, int y){result[y] = true;for(int i=1; i<matrix.size(); i++){if(matrix[y][i] && !result[i]) dfs(matrix, visited, result, y, i);}}
int main(){int n,k;cin>>n>>k;vector<vector<int>> matrix(n+1, vector<int>(n+1, 0));vector<bool> result(n+1, false); // result[1] = 1;int row,col;for(int i=0; i<k; i++){cin>>row>>col;matrix[row][col] = 1;}for(int j=1; j<=n; j++) {if(!result[j] && matrix[1][j]){dfs(matrix, result, 1, j);}}for(int i=2; i<=n; i++) {if(!result[i]){cout << -1 << endl;return 0;}}cout<<1<<endl;return 0;
}

邻接表

// c++
#include<bits/stdc++.h>
using namespace std;
int direction[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
void dfs(const vector<list<int>> &matrix,vector<bool> &result, int x){result[x] = true;list<int> keys = matrix[x];for(int key: keys){if(!result[key]){dfs(matrix, result, key);}}}
int main(){int n,k;cin>>n>>k;vector<list<int>> matrix(n+1);vector<bool> result(n+1, false); int row,col;for(int i=0; i<k; i++){cin>>row>>col;matrix[row].push_back(col);}dfs(matrix, result, 1);for(int i=1; i<=n; i++) {if(!result[i]){cout << -1 << endl;return 0;}}cout<<1<<endl;return 0;
}

106. 岛屿的周长

题目地址

遍历图，当计算每一个岛屿方格的外周长。

初始状态下单个方格的周长为4。若当前方格的上下左右四个方向有相邻的岛屿方格，则减去相邻方格数（重合边数）即为当前方格的外周长。将所有岛屿方格的外周长求和即为本题答案。

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

深搜

// c++
#include<bits/stdc++.h>
using namespace std;
int direction[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
void dfs(const vector<vector<int>> &matrix,vector<vector<bool>> &visited,int &result, int x, int y){visited[x][y] = true;// 单个方格(x,y)的周长int count = 4;for(int i=0; i<4; i++){int nextx = x + direction[i][0];int nexty = y + direction[i][1];if(nextx>=matrix.size()|| nexty>=matrix[0].size()|| nextx<0 || nexty<0) {continue;}if(matrix[nextx][nexty]) {// 减去重合边count--;if(!visited[nextx][nexty]) dfs(matrix, visited, result, nextx, nexty);}}// cout<<x<<" "<<y<<" "<<count<<endl;result += count;        
}
int main(){int n,m;cin>>n>>m;vector<vector<int>> matrix(n, vector<int>(m, 0));vector<vector<bool>> visited(n, vector<bool>(m, false));for(int i=0; i<n; i++){for(int j=0; j<m; j++){cin>>matrix[i][j];// cout<<matrix[i][j]<<" ";}// cout<<endl;}int result=0;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(matrix[i][j] && !visited[i][j]){dfs(matrix, visited, result, i, j);}}}cout<<result;return 0;
}

简化代码

其实无需深搜既可实现本题目标，只需要查看每个岛屿单元格的外周长，直接遍历邻接矩阵就可以实现。

时间复杂度： $O(n^2)$
空间复杂度： $O(1)$

// c++
#include<bits/stdc++.h>
using namespace std;
int direction[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
int main(){int n,m;cin>>n>>m;vector<vector<int>> matrix(n, vector<int>(m, 0));for(int i=0; i<n; i++){for(int j=0; j<m; j++){cin>>matrix[i][j];}}int result=0;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(matrix[i][j]){// 初始化单元格周长int count = 4;// 查看四个方向for(int k=0; k<4; k++){int nextx = i + direction[k][0];int nexty = j + direction[k][1];// 越界if(nextx>=matrix.size()|| nexty>=matrix[0].size()|| nextx<0 || nexty<0) {continue;}if(matrix[nextx][nexty]) {// 减去重合边count--;}}   // cout<<i<<" "<<j<<" "<<count<<endl;result += count;}}}cout<<result;return 0;
}