[UVa] 10562 - Undraw the Tree

主要以深度優先搜尋DFS，遞迴整棵樹，邊遞迴邊輸出



#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <cctype>
char tree[300][300];
int k=0; //the high of the input tree
void dfs(int r,int c){
 printf("%c(",tree[r][c]);
 if(r+1<k && tree[r+1][c]=='|'){ //邊界要注意
  int i=c;
  while(i-1>=0 && tree[r+2][i-1]=='-')i--;
  while(tree[r+2][i]=='-' && tree[r+3][i]!='\0'){
   if(tree[r+3][i]!=' ' && tree[r+3][i]!='\n')dfs(r+3,i); 
   //上面這邊一定要判斷換行和空白
   i++;
  }
 }
 printf(")");
}
int main(){
 freopen("input.txt","r",stdin);
 int T;
 scanf("%d",&T);
 getchar();
 while(T--){
  memset(tree,0,sizeof(tree));
  k=0;
  while(fgets(tree[k],sizeof(tree[k]),stdin)){
   //printf("%s",tree[k]);
   if(tree[k][0]=='#')break;
   else k++;
  }
  printf("(");
  if(k){
   for(int i=0;i<strlen(tree[0]);i++){
    if(tree[0][i]!=' '){ //這邊也是要以空白為判斷
     //printf("%c\n",tree[0][i]);
     dfs(0,i);
     break;
    }
   }
  }
  printf(")\n");
 }
 return 0;
}

Raspberry 安裝簡記

為了架設VPN伺服器

買了一張 Raspberry Pi II Model B

效能上比起第一代好多了

記憶卡要移植最新的系統，不然無法開機

網路設定檔如下：

/etc/network/interfaces : 

allow-hotplug wlan0 #熱插拔
iface wlan0 inet manual #手動設定
wpa-roam /etc/wpa_supplicant/wpa_supplicant.conf #使用 wpa_supplicant 設定網路參數

/etc/wpa_supplicant/wpa_supplicant.conf :

network={
  ssid="xxxxxxx"                  # SSID
  psk="xxxxxx"                    # Password
  proto=RSN                       # WPA2 加密協定
  pairwise=CCMP                   # WPA2 加密協定
  key_mgmt=WPA-PSK                # WPA2 金鑰管理協定
  auth_alg=OPEN                   # WPA2 認證演算法
}


這樣開機就能用無線網卡找到基地台了

[UVA] 10129 - Play on words

本題的要求是確認是否為有向的連通圖
運用了尤拉圖概念
先判定各字母節點的入度與出度
僅有兩個節點的入度會不等於出度(起點和終點)
DFS確認是否連通

程式碼參考《入門經典》一書，及CSDN網友shuangde800 的部落格

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
int N;
int G[100][100];
int in[100];
int out[100];
int visit[100];    //visited or not
int dfs(int a);
int main(){
    freopen("input.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
      memset(in,0,sizeof(in));
      memset(out,0,sizeof(out));
      memset(G,0,sizeof(G));
      scanf("%d",&N);
      while(N--){
        string input;
        cin >> input;
        out[input[0]-'a']++;
        in[input[input.size()-1]-'a']++;
        G[input[0]-'a'][input[input.size()-1]-'a']++;
      }
      int cnt1=0,cnt2=0;
      int ok=1;
      //找出入度不等於出度的節點
      for(int i=0;i<100;i++){
        if(!ok)break;
        if(in[i]!=out[i]){
          if(in[i]==out[i]+1)cnt1++;
          else if(out[i]==in[i]+1)cnt2++;
          else {
            ok=0; break;
          }
        }
      }
      //判別是否只有兩個節點入度與出度不同
      if(cnt1 && cnt2 && cnt1+cnt2>2)ok=0;
  
      if(ok){
        memset(visit,0,sizeof(visit));
        for(int i=0;i<100;i++)
          if(out[i]){ //找到出發點，開始DFS
            dfs(i);
            break;
          }
        int ok2=1;
        for(int i=0;i<100;i++){
          if(in[i] && !visit[i]){ok2=0; break;}
          if(out[i] && !visit[i]){ok2=0; break;}
        }
        if(ok2){
          printf("Ordering is possible.\n");
        }
        else printf("The door cannot be opened.\n");
      }
      else printf("The door cannot be opened.\n");
                   
    }
    return 0;
}

//DFS確認是否連通
int dfs(int a){
    visit[a]=1;
    for(int i=0;i<100;i++){
        if(G[a][i] && !visit[i]){
          dfs(i);
        }
    }
}