9/30 武陵資讀

基礎圖論

Grid Graph

ocean / land

• DFS
• BFS
  ZJ b701

#include<bits/stdc++.h>
using namespace std;
int r,c,sum;
int W=513,N=513,E=-1,S=-1;
void check(int i,int j){
  if(i<N) N=i;
  if(i>S) S=i;
  if(j<W) W=j;
  if(j>E) E=j;
}
int pos[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
vector<vector<int> > graph;
void DFS(int i,int j){
  sum++;
  check(i,j);
  graph[i][j]=-1;
  for(auto I:pos){
    if(graph[i+I[0]][j+I[1]]==1){
      DFS(i+I[0],j+I[1]);
    }
  }
}
int main(){
  cin.tie(0);
  cin.sync_with_stdio(0);
  cin>>r>>c;
  graph.resize(r,vector<int>(c));
  for(int i=0;i<r;i++)for(int j=0;j<c;j++) cin>>graph[i][j];
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(graph[i][j]==1){
        DFS(i,j);
        cout<<W<<" "<<N<<" "<<E<<" "<<S<<" "<<sum<<'\n';
        W=513,N=513,E=-1,S=-1,sum=0;
      }
    }
  }
  return 0;
}

Maze shortest path

• BFS
  ZJ a982

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(0);ios_base::sync_with_stdio(0);
int n;
int pos[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
inline bool in(int x,int y){
    return (1<=x&&x<n-1&&1<=y&&y<n-1 );
}
int main(){
    IOS
    bool flag=false;
    char ch;
    int cur=0,ans;
    cin>>n;
    int graph[n][n];
    pair<int,int> Start={2,2},End={n-1,n-1};
    memset(graph,0,n*n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>ch;
            graph[i][j]=(ch=='#' ? -1:0);
        }
    }
    queue<pair<int,int> > q;
    q.push(Start);
    graph[1][1]=1;
    while(q.size()){
        int x_=q.front().first,y_=q.front().second;
        if(q.front()==End){
            ans=graph[x_-1][y_-1];
            flag=true;
            break;
        }
        for(int i=0;i<4;i++){
            int X=x_+pos[i][0],Y=y_+pos[i][1];
            if(in(X-1,Y-1)){
                if(!graph[X-1][Y-1]){
                    graph[X-1][Y-1]=graph[x_-1][y_-1]+1;
                    q.push({X,Y});
                }
            }
        }
        q.pop();
    }
    if(flag) cout<<ans;
    else cout<<"No solution!";
    return 0;
}

• BFS 8 direction
  ZJ b059

#include<bits/stdc++.h>
using namespace std;
#define N 100
int n,x,y;
int Graph[101][101];
int pre[4][2]={{-1,0},{0,-1},{1,0},{0,1}},pos[4][2][2]={ { {-3,1},{-3,-1} } , { {-1,-3},{1,-3} } , { {3,-1},{3,1} } , { {-1,3},{1,3} } };
pair<int,int > Start,End,cur;
void slove(){
    bool flag=false;
    memset(Graph,0,sizeof(Graph));
    for(int i=0;i<n;i++){
        cin>>x>>y;
        Graph[x][y]=-1;
    }
    cin>>x>>y;
    Start={x,y};
    cin>>x>>y;
    End={x,y};
    queue<pair<int,int> > q;
    q.push(Start);
    Graph[Start.first][Start.second]=1;
    while(q.size()){
        cur=q.front();
        x=cur.first,y=cur.second;
        if(x==End.first&&y==End.second){
            flag=true;
            break;
        }
        q.pop();
        for(int i=0,X,Y;i<4;i++){
            X=x+pre[i][0],Y=y+pre[i][1];
            if(X<0||X>=N||Y<0||Y>=N||Graph[X][Y]==-1) continue;
            
            for(int j=0;j<2;j++){
                X=x+pos[i][j][0],Y=y+pos[i][j][1];
                if(X<0||X>=N||Y<0||Y>=N||Graph[X][Y]!=0) continue;
                
                Graph[X][Y]=Graph[x][y]+1;
                q.push({X,Y});
                
            }
            
        }
    }

    if(flag){
        cout<<Graph[End.first][End.second]-1<<'\n';
    }
    else{
        cout<<"impossible\n";
    }
}
int main(){
    cin.tie(0);ios_base::sync_with_stdio(0);
    
    while(cin>>n){
        slove();
    }
    return 0;
}

Graph

Graph presentation

ZJ f668

• Adjacency Matrix
• Adjacency List

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(0);ios_base::sync_with_stdio(0);
int n,m,a,b;
void slove(){
    vector<vector<int> > graph(n+1,vector<int >(n+1,0));
    while(m--){
        cin>>a>>b;
        graph[a][b]=b,graph[b][a]=a;
    }
    for(int i=1;i<=n;i++){
        cout<<i<<": ";
        for(int j=1;j<=n;j++){
            if(graph[i][j]) cout<<graph[i][j]<<' ';
        }
        cout<<'\n';
    }
}
int main(){
    IOS
    while(cin>>n>>m){
        slove();
    }
    return 0;
}

tags: 武陵資讀