Notes for Kali penetration and Version control tools

Version Control

• RCS: file revisions on single machine
• CVS: offer extensive archiving and merging capabilities, keeping a central repository somewhere on the network

Penetration Test

• offline attack : hash crack
• hash-identifier
• hashcat (http://hashcat.net/wiki/)
• rtgen: Rainbow Crack (空間換時間)
• rtsort
• rcrack
• samdump2: crack password of Windows account
• John (John the Ripper/John)
• unshadow
• john
• C\%windows%\system32/config
• /etc/shadow, /etc/passwd
• ophcrack: crack Windows hash

[UVa] 524 Prime Ring Problem

運用Backtrack的技巧
一直卡在輸出的最後多出空格，導致PE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cstdio>
using namespace std;
int is_prime(int a){
for(int i=2;i*i<=a;i++){
if(a%i==0)return 0;
}
return 1;
}

int sol[20];
void backtrack(int n, int m){
sol[1]=1;
if(n==m+1){
if(!is_prime(sol[1]+sol[m]))return ;
printf("1");
for(int i=2;i<=m;i++)printf(" %d",sol[i]); printf("\n");
return ;
}
for(int i=2;i<=m;i++){
int ok=1;
for(int j=2;j<n;j++){
if(sol[j]==i)ok=0;
}
if(ok){
if(is_prime(i+sol[n-1])){
sol[n]=i;
backtrack(n+1,m);
}
}
}
}
int main(){
freopen("input.txt","r",stdin);
int N,kase=0;
while(scanf("%d",&N)!=EOF){
if(kase++)printf("\n");
//memset(sol,0,sizeof(sol));
printf("Case %d:\n",kase);
backtrack(2,N);
} 
}

"BackTrack" Practice

列出所有0~4的排列組合

#include <stdio.h>
#include <stdlib.h>
int* A;
int sol[5];
void backtrack(int n){
    if(n==5){
        for(int i=0;i<n;i++)printf("%d ",sol[i]);
        printf("\n");
        return ;
    }
    for(int i=0;i<5;i++){
        int ok=1;
        for(int j=0;j<n;j++){
            if(sol[j]==i)ok=0;
        }
        if(ok){
            sol[n]=i;
            backtrack(n+1);
        }
    }
}

int main(){
    backtrack(0);
    return 0;
}

DP

Thanks my buddy tought me in a easily-understand way.

1. 遞迴
2. 筆記本
3. 下到上

f(1) = 1
f(2) = 1
f(3) = 2 = f(2) + f(1)
f(4) = f(3) + f(2)
f(5) = f(4) + f(3) = f(3) + f(2) + f(3) = f(2) + f(1) + f(2) + f(2) + f(1)

...
f(n) = f(n-1) + f(n-2)



// return f(n)
// DP
// n <= 1000
int arr[1001];
Zero(arr);
arr[1] = 1; // f(1) = 1
arr[2] = 1; // f(2) = 1
int f(int n) {
        if(arr[n] != 0) return arr[n];
        else return arr[n]=(f(n-1) + f(n-2));
}    
     
f(4) + f(3)
f(3) + f(2) + f(3)
f(2) + f(1) + f(2) + f(3)
2 + f(2) + f(3) // arr[3] = 2

int f(int n) {
        if(n == 1 || n == 2) return 1;

        // n >= 3
        int n_1 = 1 /* f(2) = 1 */,
            n_2 = 1 /* f(1) = 1 */,
            n;

        for(int i = 3; i <= n; ++i) {
                n = n_1 + n_2;
                n_2 = n_1;
                n_1 = n;
        }

        return n;
}

[UVa] 10976 - Fractions Again?!

一個簡單的暴力法
重點：將運算式作調整，可得 y = x*k / (x-k)
x : k+1 -> 2*k ，尋找 (x*k) % (x-k) == 0 的狀況
存入堆疊後列出

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <string.h>

int main(){
  int k;
  int note[10000][2];
  while(scanf("%d",&k)!=EOF){
    int total=0;
    memset(note,0,sizeof(note));
    for(int i=k+1;i<=2*k;i++){
      if((i*k)%(i-k)==0){
        note[total][0]=i;
        note[total][1]=(i*k)/(i-k);
        total++;
      }
    }
    printf("%d\n",total);
    for(int i=0;i<total;i++)
      printf("1/%d = 1/%d + 1/%d\n",k,note[i][1],note[i][0]);
  }
  return 0;
}

Setup Ubuntu 14.10 on Asus X205ta

因為X205的架構非常獨特，Linux對其硬體的支援度非常弱（據說kernel4.0之後有所改善，這倒還需要研究一番），目前的進度是將Ubuntu系統塞進32Gb的固態碟中，並設定能自動抓取開機磁區，之後可能還要針對WIFI、音效、快捷鍵和讀卡機等週邊設備進行設定。


1) 用Rufus製作開機磁碟，設定GPT partition scheme for UEFI computer，filesystem為fat32即可，將iso檔燒錄進去，並將bootia32.efi放進boot/efi/EFI底下

2) 進入BIOS，將Secure Boot Control關掉，USB Controller 改成EHCI

3) 重新開機，按Esc進入開機選單，選擇USB開機，安裝系統過程中因為mmcblk0rpmb會不斷有讀寫錯誤訊息，過程會停頓許久，需耐心等待

4) 到選擇安裝模式的畫面時，選擇將硬碟上所有資料清除，全部安裝為Ubuntu，記得選32Gb的那一塊，其他不要動

5) 安裝完成後重開機，請再次使用USB開機，進入Grub畫面，按下c進入指令行，輸入下列命令：

linux (hd1,gpt2)/boot/vmlinuz-3.16-0-23-generic root=/dev/mmcblk0p2 reboot=pci,force 

initrd (hd1,gpt2)/boot/initrd-3.16-0-23-generic 

boot

P.S. 安裝完系統後，分割區掛載分別為：

• /boot = /dev/mmcblk0p1
• / = /dev/mmcblk0p2

6) 初次進入系統後，在終端機進行bootia32.efi的建置(為了使EFI晶片能辨識硬碟內Ubuntu之開機磁區)

• apt-get install git bison libopts25 libselinux1-dev autogen m4 autoconf help2man libopts25-dev flex libfont-freetype-perl automake autotools-dev libfreetype6-dev texinfo 

     # from http://www.gnu.org/software/grub/grub-download.html 

• git clone git://git.savannah.gnu.org/grub.git 
• cd grub 
• ./autogen.sh 
• ./configure --with-platform=efi --target=i386 --program-prefix="" 
• make
•  cd grub-core 
• ../grub-install -d . --efi-directory /boot/efi/ --target=i386 
• cd /boot/efi/EFI 
• cp grub/grubia32.efi ubuntu/

目前這樣可以在開機後順利進入Ubuntu系統，至於週邊驅動的問題解決後再附上。



-------------6/30/2015
經資料查找，應該會先更新Kernel，參考連結如下：
http://magiclen.org/ubuntu-kernel-update/

一些硬體設定參考這兩篇：
http://magiclen.org/asus-x205ta-linux-mint-17/
https://wiki.debian.org/InstallingDebianOn/Asus/X205TA

Sound:
http://www.jfwhome.com/2014/03/07/perfect-ubuntu-or-other-linux-on-the-asus-transformer-book-t100/

成功再貼上

-------------7/4/2015-------------
讀卡機和WIFI設定OK，Kernel更新至4.1.0，Battery status恢復正常
聲音還未成功
觸控版手掌偵測未完成


關閉觸控板(加入至.bashrc)
xinput -disable 12
#可用xinput -list查看設備

修復於Compiz桌面下，Alt+Tab切換視窗無效

先安裝Compiz Config Setting Manager
$sudo apt-get install compizconfig-settings-manager

再裝Plugin
$sudo apt-get install compiz-plugin-main

運行ccsm，將static application switcher點選即可


-------------10/21/2015-------------
如果要修復開機時mmcblk0rpmb 的timeout問題
可以試試看這個：
https://linuxnorth.wordpress.com/2014/08/27/t100-timeout-issue-solved/

Install linux on ASUS X205

website notes here:

DebianOn : https://wiki.debian.org/InstallingDebianOn/Asus/X205TA
Mint 17: http://magiclen.org/asus-x205ta-linux-mint-17/
Ubuntu : https://github.com/lopaka/instructions/blob/master/ubuntu-14.10-install-asus-x205ta.md

http://askubuntu.com/questions/610456/ubuntu-on-asus-eeebookx205-with-all-peripherals
https://help.ubuntu.com/community/EeePC/Fixes
https://wiki.debian.org/InstallingDebianOn/Asus/X205TA
http://ubuntuforums.org/showthread.php?t=2254322
http://brownbro.github.io/blog/2015/01/15/asus-x205ta-with-lubuntu/

[UVa] 11059 - Maximum Product

暴力求解可得


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <iostream>
#include <cstdio>
#include <sstream>
using namespace std;
int main(){
  int N, i, k, kase=0;;
  string line;
  while(scanf("%d",&N)!=EOF){
    kase++;
    long long int S[N];
    getchar();
    
//Input S[0]~S[N-1]
    getline(cin,line);
    i=0,k=0;
    long long int x;
    stringstream ss(line);
    while(ss>>x){
      S[i]=x;
      i++;
    }
    
    
    int ok=0;
    long long int max=0,tmp;

//count in brute-force    
    for(i=0;i<N;i++){
      tmp = 1;
      for(int j=i;j<N;j++){
        tmp = tmp * S[j];
        if(tmp > max) max = tmp;
      }
    }

    cout << "Case #" << kase << ": The maximum product is " 
         << max << "." ;
    printf("\n\n");
  }

  return 0;
}

[UVa] 725 - Division

以Brute-force去求解
輸入N，求 N = abcde / fghij
而a~j為0~9的數字，互相不重複
每兩個輸出間要空行，而最後以0結束時又不能多空行

#include <stdio.h>
#include <stdlib.h>
#include <string>
using namespace std;

int N,a,b; // a / b
int main(){
  scanf("%d",&N);
  while(1){
    int ok=0;
    if(N==0)break;
    else {
      for(int k=0;k<100000;k++){
        int b1 = k/10000,
        b2 = k%10000/1000,
        b3 = k%10000%1000/100,
        b4 = k%10000%1000%100/10,
        b5 = k%10000%1000%100%10;
        //printf("%d %d %d %d\n",b1,b2,b3,b4);
        if(b1!=b2 && b1!=b3 && b1!=b4 && b1!=b5 && b2!=b3 && b2!=b4 && b2!=b5
        && b3!=b4 && b3!=b5 && b4!=b5){
          b = k;
          //printf("%d ",b);
          a = b*N;
          if(a/10000 >=10)break;
          else {
            int a1 = a/10000,
            a2 = a%10000/1000,
            a3 = a%10000%1000/100,
            a4 = a%10000%1000%100/10,
            a5 = a%10000%1000%100%10;
            if(   a1!=a2 && a1!=a3 && a1!=a4 && a1!=a5
               && a1!=b1 && a1!=b2 && a1!=b3 && a1!=b4 && a1!=b5
               && a2!=a3 && a2!=a4 && a2!=a5
               && a2!=b1 && a2!=b2 && a2!=b3 && a2!=b4 && a2!=b5
               && a3!=a4 && a3!=a5
               && a3!=b1 && a3!=b2 && a3!=b3 && a3!=b4 && a3!=b5
               && a4!=a5 && a4!=b1 && a4!=b2 && a4!=b3 && a4!=b4 && a4!=b5
               && a5!=b1 && a5!=b2 && a5!=b3 && a5!=b4 && a5!=b5
              )
            {
              printf("%05d / %05d = %d\n",a,b,N); 
              ok=1;
            }
          }
        }
      }
        if(ok==0)printf("There are no solutions for %d.\n",N);
    }
    scanf("%d",&N);
    if(N==0)break; else puts("");

  }
    return 0;
}




Ruija Liu 的神奇寫法
將運算式轉為字串
按照大小排序後，直接檢查0~9是否有缺數字
即可作為題目限制的判定

// UVa725 Division
// Rujia Liu
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main() {
  int n, kase = 0;
  char buf[99];
  while(scanf("%d", &n) == 1 && n) {
    int cnt = 0;
    if(kase++) printf("\n");
    for(int fghij = 1234; ; fghij++) {
      int abcde = fghij * n;
      sprintf(buf, "%05d%05d", abcde, fghij);
      if(strlen(buf) > 10) break;
      sort(buf, buf+10);
      bool ok = true;
      for(int i = 0; i < 10; i++)
        if(buf[i] != '0' + i) ok = false;
      if(ok) {
        cnt++;
        printf("%05d / %05d = %d\n", abcde, fghij, n);
      }
    }
    if(!cnt) printf("There are no solutions for %d.\n", n);
  }
  return 0;
}

[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);
        }
    }
}

[UVa] 10305 - Ordering Tasks

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <iostream>
using namespace std;
int main(){
  int n,m;
  
  while(scanf("%d %d",&n,&m)){ //n=tasks, m = pair of "<"
    if(!n && !m)break;

    int pre[n]; //入度
    int has[n]; //刪除與否
    int out[n][n]; //出邊
    for(int i=0;i<n;i++)has[i]=1;  //初始化拜訪
    memset(pre,0,sizeof(pre));
    memset(out,0,sizeof(out));
    //輸入約束組
    for(int i=0;i<m;i++){
      int a,b;
      scanf("%d %d",&a,&b);
      a--;
      b--;
      pre[b]++;
      out[a--][b]=1;
    }
    while(1){

      for(int i=0;i<n;i++){
        if(pre[i]==0 && has[i]==1){
          printf("%d",i+1);
          has[i]=0; //delete
          for(int j=0; j<n ;j++){
            if(out[i][j]==1 && i!=j){
              out[i][j]=0;
              pre[j]--;
            }
          }
          break;
        }
      }
      int stop=1;
      for(int i=0;i<n;i++){
        if(has[i]==1){
          stop = 0;
          printf(" ");
          break;
        }
      }
      if(stop==1)break;
    }
      printf("\n");
    
  }




  return 0;
}

Tor 安裝筆記

因是在不具有root權限的環境下安裝

先下載tor:https://www.torproject.org/dist/tor-0.2.5.12.tar.gz

下載libevent:http://libevent.org/

安裝libevent於家目錄:

(參考http://superuser.com/questions/324613/installing-a-library-locally-in-home-directory-but-program-doesnt-recognize-it)

cd $HOME/library/installation/folder
DIR=$HOME/local
./configure --prefix=$DIR 
#... make ... make install 

Now, to install the program, I also had to include the library packages:

cd $HOME/program/installation/folder
./configure --prefix=$DIR CFLAGS="-I$DIR/include" LDFLAGS="-L$DIR/lib"
#... make ... make install 

到tor的目錄底下並安裝:

./configure --prefix=$HOME/testing --with-libevent-dir=$HOME/testing
make install

[UVa] 816 - Abbott's Revenge

這題相對起來複雜許多
參考《入門經典》一書的作法
因書頁內容是節錄，要架構整個程式挺花時間的

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int r0,c0,r1,c1,r2,c2,dir;

struct Node{
    int r; //縱軸
    int c; //橫軸
    int dir; //進入方向
    Node(int r=0, int c=0, int dir=0):r(r),c(c),dir(dir){} //(r,c,dir)
};

void print_ans(Node u);

const char* dirs = "NESW";
const char* turns = "FLR";
//dir_id將回傳[c這個字母在dirs字串中的位址 - dirs的開頭位址]
//即是回傳c在dirs中是第幾項
//turn_id如法炮製
int dir_id(char c) {return strchr(dirs,c) - dirs;}
int turn_id(char c) {return strchr(turns,c) - turns;}

// 方向編號圖如下:
//     0
//   3   1
//     2
const int dr[]={-1,0,1,0};
const int dc[]={0,1,0,-1};
//行走函數，根據目前狀態和轉彎方式，回傳下一個節點的值
Node walk(const Node& u, int turn){
    int dir = u.dir;
    if(turn == 1)dir = (dir+3) %4; //若turn為L(在turns位置為1)則逆時針
    if(turn == 2)dir = (dir+1) %4; //若turn為R(turns位置為2)則順時針
    return Node(u.r+dr[dir], u.c+dc[dir], dir); //回傳新的節點
}

//確保下一點是存在的節點
bool inside(int r, int c){
    return  r>=1 && r<=9 && c>=1 && c<=9;
   
}


int d[10][10][4]; //初始狀態到(r,c,dir)的最短路徑長度
Node p[10][10][4]; //(r,c,dir)之父節點
int has_edge[10][10][4][3];
//路標，has_edge[r][c][dir][turn]表示(r,c,dir)是否可沿turn方向行走

void solve(){
    queue<Node> q;
    memset(d,-1,sizeof(d));
    Node u(r1,c1,dir);
    d[u.r][u.c][u.dir]=0;
    q.push(u);
    while(!q.empty()){
        Node u = q.front(); q.pop();
        if(u.r == r2 && u.c == c2) {
            print_ans(u); return;
        }
        for(int i=0;i<3;i++){
            Node v = walk(u,i);
            if(has_edge[u.r][u.c][u.dir][i] && inside(v.r, v.c)
            && d[v.r][v.c][v.dir] <0){
                d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] +1 ;
                p[v.r][v.c][v.dir] = u;
                q.push(v);
            }
        }
    }
    printf("  No Solution Possible\n");
}

void print_ans(Node u){
    vector<Node> nodes;
    for(;;){
        nodes.push_back(u);
        if(d[u.r][u.c][u.dir] ==0) break;
        u = p[u.r][u.c][u.dir];
    }
    nodes.push_back(Node(r0,c0,dir)); //放入出發點

    int count = 0;
    for(int i=nodes.size()-1; i>=0; i--){
        if(count%10 == 0)printf(" ");
        printf(" (%d,%d)", nodes[i].r, nodes[i].c);
        if(++count %10 == 0)printf("\n");
    }
    if(nodes.size() %10 !=0) printf("\n");
}

int main(){
    freopen("input.txt","r",stdin);

    string maze_name;
    while(1){
        cin >> maze_name;
        if(maze_name == "END")break;
        else cout << maze_name << '\n';

        memset(has_edge,0,sizeof(has_edge));
        //memset(p,0,sizeof(p));

        char input_dir[99];
      scanf("%d%d%s%d%d",&r0,&c0,input_dir,&r2,&c2);
        dir = dir_id(input_dir[0]);
        r1 = r0+dr[dir];
        c1 = c0+dc[dir];

        while(1){
            int input_r,input_c;
            scanf("%d",&input_r);
            if(input_r==0)break;
            scanf("%d",&input_c);
            //printf("%d %d\n",input_r,input_c);
            char input_flag[100];
            while(scanf("%s",input_flag)==1 && input_flag[0]!='*'){
                //cout << input_flag;
                for(int i=1;i<strlen(input_flag);i++){
                    has_edge[input_r][input_c][dir_id(input_flag[0])][turn_id(input_flag[i])]=1;
                }
            }
        }
        solve();
    }

    return 0;
}

[UVa] 10189 - Minesweeper

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
  //freopen("input.txt","r",stdin);
  int n,m;
  int kase = 0;
  while(scanf("%d %d",&n,&m)){
    if(n==0 && m==0)break;
    if(kase!=0)printf("\n");
    char field[n][m];
    int field_out[n][m];
    memset(field_out,0,sizeof(field_out));
    getchar();
    for(int i=0;i<n;i++){
      fgets(field[i],1000,stdin);
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        if(field[i][j]=='*'){
          int nx,ny;
          for(nx=-1;nx<=1;nx++){
            for(ny=-1;ny<=1;ny++){
              if(field[i+ny][j+nx]!='*' && i+ny>=0 && i+ny<n && j+nx>=0 && j+nx<m)
                field_out[i+ny][j+nx]++;
            }
          }
          field_out[i][j]=-1;
        }
      }
    }

    printf("Field #%d:\n",++kase);
    //print the field
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        if(field_out[i][j]==-1)printf("*");
        else printf("%d",field_out[i][j]);
      }
      printf("\n");
    }
  }
  return 0;
}

[UVa] 1225 - Digit Counting

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int count[10]; //count the apperance of 0~9
int main(){
  int kase;
  scanf("%d",&kase);
  while(kase--){
    memset(count,0,sizeof(count));
    int input;
    scanf("%d",&input);
    //printf("INPUT=%d\n",input);
    for(int i=1;i<=input;i++){
      int tmp = i;
      while(tmp){
        int m = tmp%10;
        tmp = tmp/10;
        count[m]++;
      }
    }
    for(int i=0;i<9;i++)printf("%d ",count[i]);
    printf("%d\n",count[9]);
  }
  return 0;
}

[UVa] 1103 - Ancient Messages

這題的特點就是要採用三次的floodfill方法
1. 先將背景的白點floodfill轉換成'-'
2. 再找到黑點，並將黑點區域floodfill
3. 在上一個過程中如發現白點，則floodfill並計數

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int H,W;
char* hex2bin(char ch);
void dfs(int y, int x);
void dfs2(int y, int x);
void dfs3(int y, int x);
char image[210][210]; //image[y][x]
int count=0;
char result[100];
int main(){
    freopen("input.txt","r",stdin);
    int kase=0;
    while(scanf("%d %d",&H ,&W)!=EOF){
        if(H==0 && W==0)break;
        memset(image,0,sizeof(image));
        for(int i=0;i<100;i++)result[i]='\0';
        getchar();

        char input[60];
        for(int flag=0;flag<H;flag++){   
            int flag2=0; //轉為二進位時每一列使用的旗標
            fgets(input,sizeof(input),stdin);
            for(int i=0;i<sizeof(input);i++){
                char* s = hex2bin(input[i]); //s存放二進位
                for(int j=0;j<4;j++){
                    image[flag][flag2++]=s[j]; //s依序存入image的每一列
                }
            }
        }

        //dfs(0,0);
        //clear background
       
        for(int i=0;i<W*4;i++){
            if(image[0][i]=='0'){
                dfs(0,i);
            }
        }
        for(int i=0;i<W*4;i++){
            if(image[H-1][i]=='0'){
                dfs(H-1,i);
            }
        }
        for(int i=0;i<H;i++){
            if(image[i][0]=='0'){
                dfs(i,0);
            }
        }
        for(int i=0;i<H;i++){
            if(image[i][W*4-1]=='0'){
                dfs(i,W*4-1);
            }
        }
       
        /*
        //print whole image
        for(int i=0;i<H;i++){
            for(int j=0;j<W*4;j++){
                printf("%c",image[i][j]);
            }
                printf("\n");
        }
        */

        //put result into result[]
        int tmp=0;
        for(int i=0;i<H;i++){
            for(int j=0;j<W*4;j++){
                if(image[i][j]=='1'){
                    dfs2(i,j);
                    if(count==0)result[tmp]='W';
                    if(count==1)result[tmp]='A';
                    if(count==2)result[tmp]='K';
                    if(count==3)result[tmp]='J';
                    if(count==4)result[tmp]='S';
                    if(count==5)result[tmp]='D';
                    tmp++;
                    //printf("count = %d\n",count);
                    count = 0;
                }
            }
        }
       
        //sort the result in alpha
        for(int i=0;i<100 && result[i]!='\0' ;i++){
            for(int j=i+1;j<100 && result[j]!='\0' ;j++){
                if(result[i]>result[j]){
                    int t = result[i];
                    result[i] = result[j];
                    result[j] = t;
                }
            }
        }

    /*   
        //print whole image
        for(int i=0;i<H;i++){
            for(int j=0;j<W*4;j++){
                printf("%c",image[i][j]);
            }
                printf("\n");
        }
*/
        printf("Case %d: ",++kase);
      for(int i=0;i<100;i++){
            if(result[i]=='\0')break;
            printf("%c",result[i]);
        }
        printf("\n");
    }
    return 0;
}



// floodfill the background into '-'
void dfs(int y, int x){
    if(x<0 || x>=W*4 || y<0 || y>=H || image[y][x]!='0') return;
    if(image[y][x]=='0')image[y][x] = '-';
    dfs(y-1,x);
    if(y-1 >= 0 && image[y-1][x]=='0') dfs(y-1,x);
    if(y+1 < H && image[y+1][x]=='0') dfs(y+1,x);
    if(x-1 >= 0 && image[y][x-1]=='0') dfs(y,x-1);
    if(x+1 < W*4 && image[y][x+1]=='0') dfs(y,x+1);
}

// to count how many holes in each graph
void dfs2(int y, int x){
    if(x<0 || x>=W*4 || y<0 || y>=H || image[y][x]=='-') return;
    if(image[y][x]=='0'){
        dfs3(y,x);
        count++;
    }

    image[y][x]='-';
    if(y-1>=0)dfs2(y-1,x);
    if(y+1<H)dfs2(y+1,x);
    if(x-1>=0)dfs2(y,x-1);
    if(x+1<W*4)dfs2(y,x+1);
   
}
// floodfill the holes
void dfs3(int y, int x){
    if(x<0 || x>=W*4 || y<0 || y>=H || image[y][x]=='-') return;
    image[y][x]='-';
    if(y-1 >= 0 && image[y-1][x]=='0') dfs3(y-1,x);
    if(y+1 < H && image[y+1][x]=='0') dfs3(y+1,x);
    if(x-1 >= 0 && image[y][x-1]=='0') dfs3(y,x-1);
    if(x+1 < W*4 && image[y][x+1]=='0') dfs3(y,x+1);
}



//change hex to bin
char* hex2bin(char ch){
    static char bin[5]={0}, error[]="####";
    static char mask[4]={8,4,2,1};
    int i;
    if((ch>='0'&&ch<='9')||(ch>='A'&&ch<='F')||(ch>='a'&&ch<='f')){
        (ch-='0') > 10 ? ch-='7' : 0;
        for(i=0;i<4;i++) bin[i] = ch & mask[i] ? '1' : '0';
        return bin;
    }
    else return error;
}

[UVa] 572 - Oil Deposits

有點像POJ2386 Lack Counting（其實幾乎一樣）
DFS用遞迴實作，遇到油田就換成*字號
每一個DFS結束後計數即可

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int m,n;
/*
    n
  *@*@
 m@**@
  *@*@
*/
char deposits[120][120];
void dfs(int x, int y){
    deposits[x][y]='*';
    int dx,dy,nx,ny;
    for(dx=-1;dx<=1;dx++){
        for(dy=-1;dy<=1;dy++){
            nx = x+dx;
            ny = y+dy;
            //printf("dx=%d dy=%d\n",dx,dy);
            if(nx>=0 && nx<m && ny>=0 && ny<n && deposits[nx][ny]=='@')
                dfs(nx,ny);
        }
    }
}
int main(){
    freopen("input.txt","r",stdin);
    while(scanf("%d %d",&m,&n)!=EOF){
      getchar(); //remove the newline char above
        if(m==0)break;
        for(int i=0;i<m;i++){
          fgets(deposits[i],sizeof(deposits[i]),stdin);
        }
        /* Print */
        /*
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                printf("%c",deposits[i][j]);
            }
            printf("\n");
        }
        */
        int count=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(deposits[i][j]=='@'){
                    dfs(i,j);
                    count++;
                }
            }
        }
        printf("%d\n",count);
    }
    return 0;
}

[UVa] 297 - Quadtrees

陣列要開大一點，不然很容易WA

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int img[35][35]; //(0~31 * 0~31)
char input[2000];
int flag;
int sol(int a, int b, int w){
    char c = input[flag];
    flag++;
    if(c=='p'){
        sol(a+w/2,b,w/2);
        sol(a,b,w/2);
        sol(a,b+w/2,w/2);
        sol(a+w/2,b+w/2,w/2);
    }
    if(c=='f'){
        for(int i=a; i<a+w; i++){
          for(int j=b; j<b+w; j++){
                img[i][j]=1;
            }
        }
    }
}
int main(){
    freopen("input.txt","r",stdin);
    int n;
    scanf("%d",&n);
    getchar();
    while(n--){
      int count=0;
        memset(img,0,sizeof(img));

    //getchar();
        memset(input,0,sizeof(input));
        fgets(input,sizeof(input),stdin);
        flag=0;
        sol(0,0,32);

        memset(input,0,sizeof(input));
        fgets(input,sizeof(input),stdin);
        flag=0;
        sol(0,0,32);
   
        for(int i=0;i<32;i++){
            for(int j=0;j<32;j++){
                if(img[i][j]==1)count++;
            }
        }
       
        printf("There are %d black pixels.\n",count);
    }
    return 0;
}

[UVa] 699 - The Falling Leaves

一樣運用遞迴方法實作


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int pile_left[100], pile_right[100];
int root=0,flag=0,flag_left=0,flag_right=0;
void sol(int nodes){
  if(nodes!=-1){
    //printf("flag=%d nodes=%d\n",flag,nodes);
    if(flag<0){
      pile_left[-flag-1] += nodes;
      if(flag_left<-flag) flag_left = -flag;
    }
    else if(flag>0){
      pile_right[flag-1] += nodes;
      if(flag_right<flag) flag_right = flag;
    }
    else root+= nodes;
  }
  int s;
  scanf("%d",&s);
  if(s!=-1){
    flag--;
    sol(s);
    flag++;
  }
  scanf("%d",&s);
  if(s!=-1){
    flag++;
    sol(s);
    flag--;
  }
  return;
}
int main(){
  freopen("input.txt","r",stdin);
  int kase=0,r;
  while(scanf("%d",&r) && r!=-1){
    kase++;
    printf("Case %d:\n",kase);
    flag=0;
    flag_left=-1;
    flag_right=-1;
    root = 0;
    memset(pile_left,0,sizeof(pile_left));
    memset(pile_right,0,sizeof(pile_right));
    sol(r);
        if(flag_left>=0)
    for(int i=flag_left-1 ; i>=0 ; i--){
      printf("%d ",pile_left[i]);
    }
    printf("%d",root);
        if(flag_right>=0)
    for(int i=0 ; i<=flag_right-1 ; i++){
      printf(" %d",pile_right[i]);
    }
    printf("\n\n");
  }

  return 0;
}

[UVa] 839 - Not so Mobile

輸入是以遞迴方式進行
判斷輸入的天平兩邊重量是否為零，來決定下一個輸入是否為子天平
也是參考《入門經典》和其他人的程式碼所提供的解法

#include <stdio.h>
#include <stdlib.h>
int eq;
int sol(){
    int W1,D1,W2,D2;
    scanf("%d %d %d %d",&W1,&D1,&W2,&D2);
    if(!W1){
        W1 = sol();
    }
    if(!W2){
        W2 = sol();
    }
    if(W1*D1!=W2*D2)eq=0;
    return W1+W2;
}
int main(){
    freopen("input.txt","r",stdin);
    int W,kase;
    scanf("%d",&kase);
    while(kase--){
        eq = 1;
        sol();
        if(eq==1)printf("YES\n"); else printf("NO\n");
        if(kase)printf("\n");
    }
   
    return 0;
}

[UVa] 548 - Tree

參考入門經典一書的程式碼
改以struct建構樹的方式進行改寫
許多細節需要注意

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <iostream>
#include <sstream>
using namespace std;
bool failed;
const int maxn = 10010;
int i=0,inorder[maxn], postorder[maxn];

struct Node{
    bool have_value;
    int v;
    Node *left, *right;
    Node():have_value(false),left(NULL),right(NULL){};
};
Node *root;

Node* newnode(){
    return new Node();
}

void remove_tree(Node* u){
    if(u==NULL)return;
    remove_tree(u->left);
    remove_tree(u->right);
    delete u;
}

Node* buildtree(int L1, int R1, int L2, int R2){
    if(L1>R1)return NULL;
    Node* u = newnode();
    u->v = postorder[R2];
    u->have_value = true;
    int p = L1;
    while(inorder[p] != u->v)p++;
    int count = p-L1; //nodes of left tree

    u->left = buildtree(L1,p-1,L2,L2+count-1);
    u->right = buildtree(p+1,R1,L2+count,R2-1);
    return u;
}

int best_sum, best;
void dfs(Node* u, int sum){
    sum = sum + u->v;
    if(u->right==NULL && u->left==NULL)
        if(sum<best_sum || (sum==best_sum && u->v < best)){
            best_sum = sum;
            best = u->v;
        }
    if(u->right){
        dfs(u->right, sum);
    }
    if(u->left){
        dfs(u->left, sum);
    }

}

/*
//顯示樹有無建立成功使用
int n=0;
vector<int> ans;
bool bfs(){
    queue<Node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty()){
        Node* u = q.front(); q.pop();
        if(!u->have_value) return false;
        ans.push_back(u->v);
        n++;
        if(u->left != NULL)q.push(u->left);
        if(u->right != NULL)q.push(u->right);
    }
    return true;
}
*/

int main(){
    string line;
    while(getline(cin,line)){
        i=0;
        int x;
        stringstream ss(line);
        while(ss>>x){
            inorder[i]=x;
            i++;
        }
        int L1=0,R1=i-1;
        //for(int k=0;k<i;k++)printf("%d\n",inorder[k]);
        i=0;
        getline(cin,line);
        stringstream ss2(line);
        while(ss2>>x){
            postorder[i]=x;
            i++;
        }
        int L2=0,R2=i-1;
        //for(int k=0;k<i;k++)printf("%d\n",postorder[k]);
       
        root = buildtree(L1,R1,L2,R2);
        best_sum = 10000000;

        dfs(root,0);
        printf("%d\n",best);
        remove_tree(root);
        /*
        bfs();
        for(int j=0;j<ans.size()-1;j++){
            printf("%d ",ans[j]);
        }
        */
    }

    return 0;
}

[UVa] 122 - Trees on the level

也是參考《入門經典》一書的方法
用結構和指標去建立樹的節點

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 300;
bool failed;
char s[maxn];
struct Node{
    bool have_value; //是否已建立
    int v; //值
    Node *left, *right; //left and right node
    Node():have_value(false),left(NULL),right(NULL){}; //建構函數
};
Node *root; //root of tree

//申請新節點的函數
Node* newnode(){
    return new Node();
}

void addnode(int v, char* s){
    int n = strlen(s);
    Node* u = root; // u 從根節點往下
    for(int i=0;i<n;i++){
        if(s[i]=='L'){
            if(u->left==NULL)u->left = newnode(); //不存在則建立新節點
            u = u->left; //往左
        }else if(s[i]=='R'){
            if(u->right==NULL)u->right = newnode();
            u = u->right;
        }
    }
    if(u->have_value)failed = true;
    u->v = v;
    u->have_value = true;
}

void remove_tree(Node* u){
    if(u==NULL) return;
    remove_tree(u->left);
    remove_tree(u->right);
    free(u);
}






//讀取資料
bool read_input(){
    failed = false;
    remove_tree(root);
    root = newnode(); //建立根節點
    while(1){
        if(scanf("%s", s)!=1) return false;
        if(!strcmp(s,"()"))break; // End
        int v;
        sscanf(&s[1], "%d", &v); //讀入節點值(數字)
        addnode(v, strchr(s,',')+1);
    }
    return true;
}

int n=0;
vector<int> ans;
bool bfs(){
    queue<Node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty()){
        Node* u = q.front(); q.pop();
        if(!u->have_value) return false; //錯誤
        ans.push_back(u->v); //增加到輸出尾部
        n++;
        if(u->left != NULL)q.push(u->left);
        if(u->right != NULL)q.push(u->right);
    }
    return true;
}

int main(){
    while(read_input()){
        if(!bfs())failed=1;
        if(failed)printf("not complete\n");
        else {
            for(int i=0;i<ans.size()-1;i++){
                printf("%d ",ans[i]);
            }
            printf("%d",ans[ans.size()-1]);
            printf("\n");
        }
    }
    return 0;
}