笔记：代码随想录算法训练营day59：110.字符串接龙、105.有向图的完全可达性、106.岛屿的周长

学习资料：代码随想录

110. 字符串接龙

卡码网题目链接（ACM模式）

还是有些许复杂，要把字符串从begin开始遍历，然后把每一个字母都换一下，看能否在字典里找到，如果能找到就入队列并记录，一直到最后。因为是广度优先，所以最先找到的就是最短的距离。

#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;int main(){int n;cin>>n;string beginStr,endStr;cin>>beginStr>>endStr;unordered_set<string> strList;string str;for(int i=0;i<n;i++){cin>>str;strList.insert(str);}queue<string> que;que.push(beginStr);unordered_map<string,int> visited;visited.insert(pair<string,int>(beginStr,1));while(!que.empty()){string curString = que.front();que.pop();int path = visited[curString];for(int i=0;i<curString.size();i++){string newWord=curString;for(int j=0;j<26;j++){char x=j+'a';newWord[i]=x;if(newWord==endStr){cout<<path+1<<endl;return 0;}if(strList.find(newWord)!=strList.end()&&visited.find(newWord)==visited.end()){visited[newWord]=path+1;que.push(newWord);}}}}cout<<0<<endl;
}

105.有向图的完全可达性

卡码网题目链接（ACM模式）

到有向图了，这道题其实还是搜索一遍看能不能搜索到

邻接表存储有向图

深搜处理当前节点：

#include <iostream>
#include <vector>
#include <list>
using namespace std;void dfs(const vector<list<int>>& graph,vector<bool>& visited,int k){if(visited[k]==true) return;visited[k]=true;list<int> keys=graph[k];for(int key:keys){dfs(graph,visited,key);}
}
int main(){int n,k;cin>>n>>k;vector<list<int>> graph(n+1);int s,t;for(int i=0;i<k;i++){cin>>s>>t;graph[s].push_back(t);}vector<bool> visited(n+1,false);dfs(graph,visited,1);               //从1出发for(int i=1;i<n+1;i++){if(visited[i]==false){cout<<-1<<endl;return 0;}}cout<<1<<endl;
}

深搜处理下一节点

#include <iostream>
#include <vector>
#include <list>
using namespace std;void dfs(const vector<list<int>>& graph,vector<bool>& visited,int k){list<int> keys=graph[k];for(int key:keys){if(visited[key]==false){dfs(graph,visited,key);visited[key]=true;}}
}
int main(){int n,k;cin>>n>>k;vector<list<int>> graph(n+1);int s,t;for(int i=0;i<k;i++){cin>>s>>t;graph[s].push_back(t);}vector<bool> visited(n+1,false);visited[1]=true;dfs(graph,visited,1);               //从1出发for(int i=1;i<n+1;i++){if(visited[i]==false){cout<<-1<<endl;return 0;}}cout<<1<<endl;
}

广搜：

#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;void bfs(const vector<list<int>>& graph,vector<bool>& visited,int k){queue<int> que;que.push(k);visited[k]=true;while(!que.empty()){int cur=que.front();que.pop();list<int> keys=graph[cur];for(int key:keys){if(visited[key]==false){que.push(key);visited[key]=true;      //谨记卡哥说的push后立马记录}}}}
int main(){int n,k;cin>>n>>k;vector<list<int>> graph(n+1);int s,t;for(int i=0;i<k;i++){cin>>s>>t;graph[s].push_back(t);}vector<bool> visited(n+1,false);bfs(graph,visited,1);               //从1出发for(int i=1;i<n+1;i++){if(visited[i]==false){cout<<-1<<endl;return 0;}}cout<<1<<endl;
}

106. 岛屿的周长

卡码网题目链接（ACM模式）

并不需要深搜或广搜了，直接暴力

1、检查每一个陆地单元的靠水的边

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2]={0,1,-1,0,0,-1,1,0};int main(){int n,m;cin>>n>>m;vector<vector<int>> fiji(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>fiji[i][j];}}int result =0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(fiji[i][j]==1){for(int k=0;k<4;k++){       //我怎么就想不到呢，每个节点都分别计算四个边啊int xnext = i+dir[k][0];int ynext = j+dir[k][1];if(xnext<0||xnext>=fiji.size()||ynext<0||ynext>=fiji[0].size()||fiji[xnext][ynext]==0){result++;}}            }}}cout<<result<<endl;
}

2、先计算所有陆地单元的数量，然后减去重复周长

#include <iostream>
#include <vector>
using namespace std;int main(){int n,m;cin>>n>>m;vector<vector<int>> fiji(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>fiji[i][j];}}int sum=0;int repeat=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(fiji[i][j]==1){sum+=4;if(i-1>=0&&fiji[i-1][j]==1) repeat+=2;   //重复一次少的是两个边if(j-1>=0&&fiji[i][j-1]==1) repeat+=2;//只刨除上面和左面的重复部分，避免重复计算}}}int result = sum-repeat;cout<<result<<endl;
}