[BFS]POI2007 山峰和山谷 grz 解題報告

Ridges and Valleys

Memory limit: 32 MB

Byteasar loves trekking in the hills. During the hikes he explores all the ridges and valleys in vicinity. Therefore, in order to plan the journey and know how long it will last, he must know the number of ridges and valleys in the area he is going to visit. And you are to help Byteasar.
Byteasar has provided you with a map of the area of his very next expedition. The map is in the shape of a square. For each field belonging to the square (for ), its height is given.
We say two fields are adjacent if they have a common side or a common vertex (i.e. the field is adjacent to the fields , , , , , , , , provided that these fields are on the map).
We say a set of fields forms a ridge (valley) if:

• all the fields in have the same height,
• the set forms a connected part of the map (i.e. from any field in it is possible to reach any other field in while moving only between adjacent fields and without leaving the set ),
• if and the field is adjacent to , then (for a ridge) or (for a valley).

In particular, if all the fields on the map have the same height, they form both a ridge and a valley.
Your task is to determine the number of ridges and valleys for the landscape described by the map.

[搜索]USACO Feb08 Silver 流星雨 meteor 解題報告

題目連結：http://cogs.yeefanblog.tk/t/138

Title: 流星雨

Input: meteor.in

Output: meteor.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

貝茜聽說了一個駭人聽聞的消息：一場流星雨即將襲擊整個農場，由於流星體積過大它們無法在撞擊到地面前燃燒殆盡，屆時將會對它撞到的一切東西造成毀 滅性的打擊。很自然地，貝茜開始擔心自己的安全問題。以FJ牧場中最聰明的奶牛的名譽起誓，她一定要在被流星砸到前，到達一個安全的地方（也就是說，一塊 不會被任何流星砸到的土地）。如果將牧場放入一個直角座標系中，貝茜現在的位置是原點，並且，貝茜不能踏上一塊被流星砸過的土地。

根據預報，一共有M顆流星(1 <= M <= 50,000)會墜落在農場上，其中第i顆流星會在時刻T_i (0 <= T_i <= 1,000)砸在座標為(X_i, Y_i) (0 <= X_i <= 300；0 <= Y_i <= 300)的格子裡。流星的力量會將它所在的格子，以及周圍4個相鄰的格子都化為焦土，當然貝茜也無法再在這些格子上行走。

貝茜在時刻0開始行動，它只能在第一象限中，平行於座標軸行動，每1個時刻中，她能移動到相鄰的（一般是4個）格子中的任意一個，當然目標格子要沒有被燒焦才行。如果一個格子在時刻t被流星撞擊或燒焦，那麼貝茜只能在t之前的時刻在這個格子裡出現。

請你計算一下，貝茜最少需要多少時間才能到達一個安全的格子。

程序名: meteor

[搜索]OI練習題：求圖形面積 area

題一 求圖形面積

【問題描述】

具有不同顏色的 N 個小的矩形的紙被疊放在一張白紙上， 紙的尺寸是寬(左右)為A， 長(上下)為B，擺放矩形時使矩形的邊與紙的邊平行，並且每個矩形必須整個放在紙的邊界之內。因此，不同顏色的各種不同圖形可在紙上出現，同一顏色的兩個區域中如果至少有一個公共點，則認為它們是同一圖形的一部分，否則認為是不同的圖形。

題目要求計算每一圖形的面積。 A ， B 是正的偶數，且均不大於30 。座標系統的定義為：座標原點在紙的中心，兩個軸分別平行於紙的兩邊。

USACO 2011 November Contest, Bronze Division Problem 4. Cow Beauty Pageant (pageant)

Problem 4: Cow Beauty Pageant (Bronze Level) [Brian Dean] 

Hearing that the latest fashion trend was cows with two spots on their hides, Farmer John has purchased an entire herd of two-spot cows. Unfortunately, fashion trends tend to change quickly, and the most popular current fashion is cows with only one spot! 

FJ wants to make his herd more fashionable by painting each of his cows in such a way that merges their two spots into one. The hide of a cow is represented by an N by M (1 <= N,M <= 50) grid of characters like this: 
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX.. 
........XXXXX...
.........XXX....

Here, each 'X' denotes part of a spot. Two 'X's belong to the same spot if they are vertically or horizontally adjacent (diagonally adjacent does not count), so the figure above has exactly two spots.
 All of the cows in FJ's herd have exactly two spots.

FJ wants to use as little paint as possible to merge the two spots into one. In the example above, he can do this by painting only three additional characters with 'X's (the new characters are marked with '*'s below to make them easier to see). 
................ 
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX... 
.........XXX.... 

Please help FJ determine the minimum number of new 'X's he must paint in order to merge two spots into one large spot. 

PROBLEM NAME: pageant 

INPUT FORMAT: 
* Line 1: Two space-separated integers, N and M.
* Lines 2..1+N: Each line contains a length-M string of 'X's and '.'s specifying one row of the cow hide pattern.

SAMPLE INPUT (file pageant.in): 
6 16 
................
..XXXX....XXX... 
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

INPUT DETAILS: 
The pattern in the input shows a cow hide with two distinct spots, labeled 1 and 2 below: 
................
..1111....222... 
...1111....22... 
.1111......222..
........22222...
.........222.... 

OUTPUT FORMAT: 
* Line 1: The minimum number of new 'X's that must be added to the input pattern in order to obtain one single spot.

SAMPLE OUTPUT (file pageant.out): 
3 

OUTPUT DETAILS:
Three 'X's suffice to join the two spots into one:
................ 
..1111....222...
...1111X...22... 
.1111..XX..222..
........22222...
.........222....

【分析】
Floodfill，可以使用廣度優先搜索。
枚舉spot1內的所有點 與 spot2內的所有點，找出兩個 橫坐標相減的絕對值與橫坐標相減的絕對值之和再減一 的最小值，輸出這個值即可。

【我的代碼（這是我改後的程序，自測AC滿分）】
/*
ID:zyfwork1
PROB:pageant
LANG:C++
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N,M;
int Mat[51][51];

int step[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int One[2600][2];
int Two[2600][2];
int topa=0;
int topb=0;

int abs(int a)
{
    return a>0?a:-a;
}

void init()
{
    scanf("%d %d\n",&N,&M);
    char c;
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=M;j++)
        {
            cin>>c;
            if(c=='.')
                Mat[i][j]=0;
            if(c=='X')
                Mat[i][j]=-1;
        }
    }
}

void bfs(int n)
{
    int Q[2600][2];
    int big=1;
    int sma=0;
    for (int i=1;i<=N;i++)
    {
        bool flag=false;
        for(int j=1;j<=M;j++)
        {
            if(Mat[i][j]==-1)
            {
                Q[0][0]=i;
                Q[0][1]=j;
                flag=true;
                break;
            }
        }
        if(flag)
            break;
    }
   
    int x,y;
    int tx,ty;
    while(sma<big)
    {
        x=Q[sma][0];
        y=Q[sma][1];
        Mat[x][y]=n;

        if(n==1)
        {
            topa++;
            One[topa][0]=x;
            One[topa][1]=y;
        }
        if(n==2)
        {
            topb++;
            Two[topb][0]=x;
            Two[topb][1]=y;
        }
       
        for (int i=0;i<4;i++)
        {
            tx=x+step[i][0];
            ty=y+step[i][1];
            if(tx>=1 && tx<=N && ty>=1 && ty<=M)
            {
                if(Mat[tx][ty]!=-1)
                    continue;
                Q[big][0]=tx;
                Q[big][1]=ty;
                Mat[tx][ty]=n;
                big++;
            }
        }
        sma++;
    }
}

int main()
{
    freopen("pageant.in","r",stdin);
    freopen("pageant.out","w",stdout);
    init();
    bfs(1);
    bfs(2);
    int ans=0x7fffffff;
    for (int i=1;i<=topa;i++)
    {
        int x=One[i][0];
        int y=One[i][1];
        for (int j=1;j<=topb;j++)
        {
            int xx=Two[j][0];
            int yy=Two[j][1];
            int tmp=abs(xx-x)+abs(yy-y);
            if( tmp<ans )
                ans=tmp;
        }
    }
    printf("%d\n",ans-1);
    return 0;
}