笔记：代码随想录算法训练营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;
}