uva 11094 Continents

用 BFS 把相鄰的土地算出來有幾個，找非國王目前位置的區域有最多相鄰土地的區

域，土地的個數即為解。所以一開始把國王目前位置用 BFS 走過，之後遇到沒有被走過的，

就用 BFS找完所有相鄰的。

注意：

1. land 有可能用 w 表示 ，因為題目沒有限定 land 和 water 是甚麼代號，所以不能把走過的地

方在地圖上標示 w。 (這題原本我是把走過的在地圖標上 w ，但是 runtime error，猜測 land 在

測資中可能有些用 w 表示)

2.右邊的邊界和左邊的邊界是互通的。



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

char maps[21][21]={0},passed[21][21]={0};
int M,N;
char land;

struct point{
    int x,y;
};

int BFS(int x,int y){
    struct point queueList[441];
    struct point tmp,newLand;
    int top,head;

    top=-1; head=0;
    queueList[++top].x=x;
    queueList[top].y=y;
    passed[x][y]=1;

    while(head<=top){
        tmp=queueList[head];
        passed[tmp.x][tmp.y]=1;

        x=tmp.x; y=(tmp.y+1)%N;
        if(maps[x][y]==land && passed[x][y]==0){
            newLand.x=x; newLand.y=y;
            queueList[++top]=newLand;
            passed[x][y]=1;
        }

        x=tmp.x+1; y=tmp.y;
        if(x<M && maps[x][y]==land && passed[x][y]==0){
            newLand.x=x; newLand.y=y;
            queueList[++top]=newLand;
            passed[x][y]=1;
        }

        x=tmp.x; y=tmp.y-1;
        if(y<0) y=N-1;
        if(maps[x][y]==land && passed[x][y]==0){
            newLand.x=x; newLand.y=y;
            queueList[++top]=newLand;
            passed[x][y]=1;
        }

        x=tmp.x-1; y=tmp.y;
        if(x>=0 && maps[x][y]==land && passed[x][y]==0){
            newLand.x=x; newLand.y=y;
            queueList[++top]=newLand;
            passed[x][y]=1;
        }

        ++head;
    }

    return top+1;
}

int main(void){
    int maximum,landSize;
    int curM,curN;
    int i,j;


    while( scanf("%d %d",&M,&N)!=EOF ){
        for(i=0;i<M;i++){
            scanf("%s",&maps[i]);
        }
        scanf("%d %d",&curM,&curN);
        land=maps[curM][curN];

        BFS(curM,curN);

        maximum=0;
        for(i=0;i<M;i++){
            for(j=0;j<N;j++){
                if(maps[i][j]==land && passed[i][j]==0){
                    landSize = BFS(i,j);

                    if(landSize>maximum) maximum=landSize;
                }
            }
        }

        printf("%d\n",maximum);

        memset(passed,0,sizeof(passed));
    }


    return 0;
}

uva 10082 WERTYU

這題為對照的方式，因為不是所有字元的對照都有共同的關係，或是少數幾種不同情況的關

係，所以需要自己建對照的方式，用 switch, if 的話，會需要寫成多行程式碼，用字串陣列的

方式把前一個的放在前面，用 loop 找到後，印出前一個即是對照的，這樣就不用多寫很多程

式碼。如果在 table 找不到 ( 搜尋的 index 超過 table 裡的個數 )，就直接印出。


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

int main(void){
    char input[10000]={0};
    char table[]="`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
    int i,j;

    while(fgets(input,10000-1,stdin)!=NULL){
        for(i=0;input[i]!='\0';i++){
            for(j=0; table[j]!=input[i] && j<strlen(table) ;j++);

            if( j==strlen(table) ) printf("%c",input[i]);
            else printf("%c",table[j-1]);
        }
    }

    return 0;
}

uva 10018 Reverse and Add

這題可以利用大數運算的加法來做，在做大數運算時，用來儲存的字串陣列，index 0 ，

從個位數開始存，這樣遇到進位的時候，可以很容易地往陣列的後面多一個數字。

這個儲存方法可以適用於加法、減法、乘法。

ex: 195 +9230

795 ->  597
9230 -> 0329

   597
 +0329
_______
   52001

從上面可以看到，位數直接對齊，增加的位數直接擺放到下一個位置。


這題用大數運算，所以一開始先把讀到的數字字串反轉。

相加的時候，再把數字字串複製的暫存陣列，把暫存陣列反轉，就可以相加了。

因為題目確定有最後會得到 palindrome，所以輸出時，直接輸出即可，不用再反轉。


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

int palindrome(char num[]){
    int i,j,ok;

    for(i=0,j=strlen(num)-1,ok=1;i<=(strlen(num)-1)/2;i++,j--){
        if(num[i]!=num[j]){
            ok=0; break;
        }
    }

    return ok;
}

void reverChar(char num[]){
    char tmp[20]={0};
    int i,j;

    strcpy(tmp,num);
    for(i=0,j=strlen(tmp)-1;j>=0;j--,i++){
        num[i]=tmp[j];
    }
    num[i]=0;

    return;
}

void add(char num1[], char num2[]){
    int i,carry=0,sum;

    for(i=0;i<=strlen(num1)-1;i++){
        sum=num1[i]-'0' + num2[i]-'0' + carry;
        if( sum > 9 ){ carry=1; sum%=10;}
        else carry=0;

        num1[i]=sum+'0';
    }
    if(carry==1)num1[i]=1+'0';
    num1[i+1]='\0';

    return;
}

int main(void){
    int amount,counter;
    char num1[20],num2[20];

    scanf("%d",&amount);
    while(1){
        amount--;

        scanf("%s",&num1);
        reverChar(num1);

        counter=0;
        while(1){
            if(palindrome(num1) == 1) break;
            ++counter;

            strcpy(num2,num1);
            reverChar(num2);
            add(num1,num2);
        }

        printf("%d %s\n",counter,num1);

        if(amount==0)break;
    }



    return 0;
}

uva 929 Number Maze

把這張格子的圖想成是一張無向圖，連結的部分只有四個方向的小格子。

只要做 dijkstra 算出左上角到右下角的最短距離即為解。

judge 時，發現到：

counter 存筆數，while(counter--)在 uva 上跑的時候，不會終止。要改成其它方式跳出。


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

struct node{
    int x;
    int y;
    int distance;
};


int maze[1000][1000]={0};
int row,column,amount;
int ans;
struct node * minHeap;
int *table;

void adjust(int index){
    struct node tmp;

    int parent,child;

    child=index;
    parent=index/2;

    tmp=minHeap[index];
    while(parent>=1){
        if(minHeap[parent].distance > tmp.distance){
            minHeap[child]=minHeap[parent];
            table[minHeap[child].x*1000 + minHeap[child].y]=child;
        }else
            break;

        child=parent;
        parent=child/2;
    }
    minHeap[child]=tmp;
    table[minHeap[child].x*1000+minHeap[child].y]=child;

    return;
}

struct node extract(){
    struct node tmp,change;
    int index,parent,child;

    tmp.distance=-1;

    if(amount==0) return tmp;

    tmp=minHeap[1];
    maze[tmp.x][tmp.y]=-1;

    change=minHeap[amount];
    --amount;

    parent=1;
    child = parent*2;
    while(child<=amount){
        if(child < amount){
            if(minHeap[child].distance > minHeap[child+1].distance)
                ++child;
        }

        if(change.distance > minHeap[child].distance){
            minHeap[parent]=minHeap[child];
            table[minHeap[parent].x*1000+minHeap[parent].y]=parent;
        }else
            break;

        parent=child;
        child=parent*2;
    }
    minHeap[parent]=change;
    table[minHeap[parent].x*1000+minHeap[parent].y]=parent;

    return tmp;
}

void dijkstra(){
    struct node tmp;

    minHeap[1].distance=maze[1][1];
    while(1){
        tmp=extract();
        if(tmp.x==row&&tmp.y==column){ ans=tmp.distance; return; }


        if( (tmp.x-1)>=1 && (tmp.y)>=1 && maze[tmp.x-1][tmp.y]!=-1)
            if(tmp.distance + maze[tmp.x-1][tmp.y] < minHeap[table[(tmp.x-1)*1000+tmp.y]].distance){
                minHeap[table[(tmp.x-1)*1000+tmp.y]].distance=tmp.distance + maze[tmp.x-1][tmp.y];
                adjust(table[(tmp.x-1)*1000+tmp.y]);
            }
        if( (tmp.x)>=1 && (tmp.y+1)<=column && maze[tmp.x][tmp.y+1]!=-1)
            if(tmp.distance + maze[tmp.x][tmp.y+1] < minHeap[table[tmp.x*1000+tmp.y+1]].distance){
                minHeap[table[tmp.x*1000+tmp.y+1]].distance=tmp.distance + maze[tmp.x][tmp.y+1];
                adjust(table[tmp.x*1000+tmp.y+1]);
            }
        if( (tmp.x+1)<=row && (tmp.y)>=1 && maze[tmp.x+1][tmp.y]!=-1)
            if(tmp.distance + maze[tmp.x+1][tmp.y] < minHeap[table[(tmp.x+1)*1000+tmp.y]].distance){
                minHeap[table[(tmp.x+1)*1000+tmp.y]].distance=tmp.distance + maze[tmp.x+1][tmp.y];
                adjust(table[(tmp.x+1)*1000+tmp.y]);
            }
        if( (tmp.x)>=1 && (tmp.y-1)>=1 && maze[tmp.x][tmp.y-1]!=-1)
            if(tmp.distance + maze[tmp.x][tmp.y-1] < minHeap[table[tmp.x*1000+tmp.y-1]].distance){
                minHeap[table[tmp.x*1000+tmp.y-1]].distance=tmp.distance + maze[tmp.x][tmp.y-1];
                adjust(table[tmp.x*1000+tmp.y-1]);
            }
    }


    return;
}

int main(void){
    int i,j,index,counter;

    minHeap = (struct node *)malloc( sizeof(struct node) * 1000 * 1000 );
    table = (int *)malloc( sizeof(int) * 1000 * 1000 );

    scanf("%d",&counter);
    while(counter--){
        scanf("%d",&row);
        scanf("%d",&column);

        amount=row*column;

        for(i=1,index=0;i<=row;i++){
            for(j=1;j<=column;j++){
                scanf("%d",&maze[i][j]);
                minHeap[++index].distance=100000;
                minHeap[index].x=i;
                minHeap[index].y=j;

                table[i*1000+j]=index;
            }
        }

        ans=0;
        dijkstra();

        printf("%d\n",ans);

        if(counter<= 0)break;
    }

    return 0;
}

uva 136 Ugly Numbers

把數字有的 2, 3, 5  因數都除掉後，若數字變成 1 ，表示數字的質因數只有 2, 3, 5。

可以用程式把數字算出來後，直接印出即可。算出第 1500 個要花一段時間。

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

int main(void){
    /*int i,counter=0,has,tmp;

    i=2; counter=1;
    while(1){
        has=0; tmp=i;

        while(tmp%2==0) tmp/=2;
        while(tmp%3==0) tmp/=3;
        while(tmp%5==0) tmp/=5;

        if(tmp==1) ++counter;

        if(counter==1500) break;

        ++i;
    }

    printf("The 1500'th ugly number is %d.\n",i);*/

    printf("The 1500'th ugly number is 859963392.\n");

    return 0;
}

uva 10189 Minesweeper

題目變成是踩地雷的反面玩法，算出地雷附近的數字為何，遇到地雷時，把周圍的格子都記

數一次，但在計數的時候，要注意可以計數的範圍，這部分可以先不用判斷周圍是否有 * 再

++，可以在 output 時再判斷 (> 8，因為周圍的格子最多被 + 8 次)，這樣可以減少判斷式的長

度。最後 output 時，兩筆 output 之間要有一空行，但最後一筆的後面不用再多一個空行。


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

int main(void){
    int row,column,i,j;
    int counter=0;
    char c;
    char board[100][100]={0};

    while(scanf("%d %d%c",&row,&column,&c)!=EOF){
        if(!row && !column) break;

        ++counter;
        if(counter>1) printf("\n");

        for(i=0;i<row;i++){
            for(j=0;j<column;j++){
                scanf("%c",&c);

                if(c=='*'){
                    board[i][j]='*';

                    if( (i-1)>=0 && (j-1)>=0 ) ++board[i-1][j-1];
                    if( (i-1)>=0 && (j)>=0 ) ++board[i-1][j];
                    if( (i-1)>=0 && (j+1)<column ) ++board[i-1][j+1];
                    if( (i)>=0 && (j-1)>=0 ) ++board[i][j-1];
                    if( (i)>=0 && (j+1)<column ) ++board[i][j+1];
                    if( (i+1)<row && (j-1)>=0 ) ++board[i+1][j-1];
                    if( (i+1)<row && (j)>=0 ) ++board[i+1][j];
                    if( (i+1)<row && (j+1)<column ) ++board[i+1][j+1];
                }
            }

            scanf("%c",&c);
        }

        printf("Field #%d:\n",counter);
        for(i=0;i<row;i++){
            for(j=0;j<column;j++){
                if(board[i][j] > 8)
                    printf("*");
                else
                    printf("%d",board[i][j]);

                board[i][j]=0;
            }
            printf("\n");
        }
    }


    return 0;
}

uva 11040 Add bricks in the wall

從最底層開始建起，當最底層的數字都是正確的時候，上面的一定可以符合。

一開始，最底層的 blank brick 先填 0，然後開始往上建。

當往上遇到 input 給定的 brick時 ：

check 是否符合，如果不符合，則調整目前層數的下一層，使符合，並在這一層往上建完後

(調整完這層所要調整的)，再從最底層開始建起，這樣的話，剛剛往下調整的層數，由下下層

做 check 時，可以繼續往下調整，


往上建的時候，注意 index：

input 給定的 brick 會和目前往上建的左 brick 的 column 相同，row - 1

往下被調整的 brick 會是目前往上建的左 brick 的 column + 1，row + 1


最後：

當需要調整時，要把 i 設為 10，因為 outer for loop 完成一次時，會做 -1 的動作。


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

int main(void){
    int amount,i,j,modify,k,m;
    int triangle[10][10]={0};

    scanf("%d",&amount);
    while(amount--){
        for(i=1;i<=9;i+=2){
            for(j=1;j<=i;j+=2){
                scanf("%d",&triangle[i][j]);
            }
        }

        for(i=9;i>1;i--){
            modify=0;
            for(j=1;j<i;j++){
                if( (i-1)%2!=0 && j%2!=0 ){
                    if(triangle[i][j]+triangle[i][j+1]!=triangle[i-1][j]){
                        triangle[i+1][j+1]+=(triangle[i-1][j]-(triangle[i][j]+triangle[i][j+1]))/2;
                        modify=1;
                    }
                }else{
                    triangle[i-1][j]=triangle[i][j]+triangle[i][j+1];
                }
            }

            if(modify==1) i=10;
        }

        for(i=1;i<=9;i++){
            for(j=1;j<i;j++){
                printf("%d ",triangle[i][j]);
                triangle[i][j]=0;
            }
            printf("%d\n",triangle[i][j]);
            triangle[i][j]=0;
        }
    }


    return 0;
}