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