欧美日韩精品欧美日韩精品 ,欧美成人午夜视频,亚洲黄色免费网站

2011分治-平面最近點對（附C++源代碼）

求平面最近點對的核心思想乃是二分，用遞歸實現。具體操作如下：

若點的個數很少（比如小于3或者小于5），就直接枚舉。

如點的個數很多，按現將所有點按X排序，并按X坐標平均的分成左右兩個部分（假設分割線為X=nx），分別求出兩邊的最短距離minl與minr并令ans=min（minl，minr）。

求出左右兩邊的最小值之后，剩下的工作就是合并。易見若該點集存在點對（a，b）的最近距離小于ans，則a，b一定分別在x=nx的兩邊，切nx-a.x與nx-b.x的絕對值肯定小于ans。

據此我們可以將點集中所有X值在（nx-ans，nx+ans）的點都選出來，那么滿足條件的（a，b）肯定都在其中。

易見若存在（a，b）兩點他們之間的距離小于ans，那么a.y-b.y的絕對值也肯定小于ans。

綜上存在（a，b）兩點他們之間的距離小于ans那，（a，b）一定在一個長為2*ans寬為ans的矩形之中。而且這個矩形被X=nx平分成兩個ans*ans的矩形，由于無論是在左邊還是在右邊，任意兩點的之間的距離總是小于等于ans的，所以兩個ans*ans 的矩形中最多只有4個點（分別在四個頂點上），長為2*ans寬為ans的矩形最多有8個點。

據此我們將所有X值在（nx-ans，nx+ans）的點按他們的Y值進行排序。依次看每個點與它之后的7個點的距離是否小于ans，若小于則更新ans，最后求出來的結果就是平面最近點對的距離。保留產生該距離的兩個點即可得到最近點對。

練手題目：Pku2107，Vijos1012

附C++代碼（Pku2107）：

#include <iostream>
#include <cmath>

const long maxsize = 100000;

typedef struct
{
double x, y;
} PointType;

long list[maxsize], listlen,n;
PointType point[maxsize];

int sortcmp(const void *,const void *);
double dis(PointType,PointType);
double getmin(double,double);
int listcmp(const void *,const void *);
double shortest(long,long);
int init(void);

int main()
{
while (init())
printf("%.2lf\n",shortest(0, n - 1)/2);
return 0;
}

int sortcmp(const void *a, const void *b)
{
if (((PointType*)a)->x < ((PointType*)b)->x)
   return -1;
else
   return 1;
}

double dis(PointType a, PointType b)
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

double getmin(double a, double b)
{
return a<b?a:b;
}

int listcmp(const void *a, const void *b)
{
if (point[*(int*)a].y < point[*(int*)b].y)
   return -1;
else
   return 1;
}

double shortest(long l, long r)
{
if (r - l == 1)
   return dis(point[l], point[r]);
if (r - l == 2)
   return getmin(getmin(dis(point[l], point[l+1]), dis(point[l], point[r])), dis(point[l+1], point[r]));
long i, j, mid = (l + r) >> 1;
double curmin = getmin(shortest(l, mid), shortest(mid + 1, r));
listlen = 0;
for (i = mid; i >= l && point[mid+1].x - point[i].x <= curmin; i --)
   list[listlen++] = i;
for (i = mid + 1; i <= r && point[i].x - point[mid].x <= curmin; i ++)
   list[listlen++] = i;
qsort(list, listlen, sizeof(list[0]), listcmp);
for (i = 0; i < listlen; i ++)
   for (j = i + 1; j < listlen && point[list[j]].y - point[list[i]].y <= curmin; j ++)
    curmin = getmin(curmin, dis(point[list[i]], point[list[j]]));
return curmin;
}

int init(void)
{
int i;
scanf("%d", &n);
for (i=0;i<n;i++)
scanf("%lf%lf",&point[i].x,&point[i].y);
qsort(point,n,sizeof(point[0]),sortcmp);
return n;
}

自己寫的代碼:

/*
* Problem(classic):
*    there're many points in a plane surface, find the nearest two points
*    see: <CLRS> 33.4 section
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define INF 0x7FFFFFFF
#define NUM_MAX 100000
#define THRESHOLD 3

struct Point {
    double x, y;
};
struct Point points[NUM_MAX];
int total, yindex[NUM_MAX];

double
min(double arg1, double arg2)
{
    return (arg1 <= arg2 ? arg1 : arg2);
}

double
distance(struct Point *arg1, struct Point *arg2)
{
    double x_diff = arg1->x - arg2->x;
    double y_diff = arg1->y - arg2->y;
    return sqrt(x_diff*x_diff + y_diff*y_diff);
}

int
compare_x(const void *arg1, const void *arg2)
{
    struct Point *p1 = (struct Point *)arg1;
    struct Point *p2 = (struct Point *)arg2;
    return (p1->x - p2->x);
}

int
compare_y(const void *arg1, const void *arg2)
{
    struct Point *p1 = points + *(int *)arg1;
    struct Point *p2 = points + *(int *)arg2;
    return (p1->y - p2->y);
}

void
init_preprocess()
{
    int i;
    scanf("%d", &total);
    for(i=0; i<total; ++i)
        scanf("%lf %lf", &points[i].x, &points[i].y);
    qsort(points, total, sizeof(struct Point), compare_x);
}

double
find_nearest(int begin, int end)
{
    int i, j;
    double ret = INF;
    if(end-begin+1 <= THRESHOLD) {
        for(i=begin; i<end; ++i) {
            for(j=i+1; j<=end; ++j)
                ret = min(ret, distance(points+i, points+j));
        }
        return ret;
    }
    int mid = begin + ((end - begin) >> 1);
    double dis = min(find_nearest(begin, mid), find_nearest(mid+1, end));
    int len = 0;
    for(j=mid; j>=begin && points[mid+1].x-points[j].x<=dis; --j)
        yindex[len++] = j;
    for(j=mid+1; j<=end && points[j].x-points[mid].x<=dis; ++j)
        yindex[len++] = j;
    qsort(yindex, len, sizeof(int), compare_y);
    ret = dis;
    for(i=0; i<=len-7; ++i) {
        for(j=i+1; j<=i+7; ++j)
            ret = min(ret, distance(points+yindex[i], points+yindex[j]));
    }
    return ret;
}

double
brute_force(int begin, int end)
{
    double ret = INF;
    int i, j;
    for(i=begin; i<end; ++i) {
        for(j=i+1; j<=end; ++j)
            ret = min(ret, distance(points+i, points+j));
    }
    return ret;
}

int
main(int argc, char **argv)
{
    init_preprocess();
    double ret = find_nearest(0, total-1);
    printf("\nNearest Distance[Brute Force]: %f\n", brute_force(0, total-1));
    printf("\nNearest Distance: %f\n", ret);
}

posted @ 2011-09-03 23:17 simplyzhao 閱讀(1176) | 評論 (1) | 編輯收藏

2011知識點-TCP 區分消息邊界[zz]

在socket網絡程序中，TCP和UDP分別是面向連接和非面向連接的。因此TCP的socket編程，收發兩端（客戶端和服務器端）都要有一一成對的socket，因此，發送端為了將多個發往接收端的包，更有效的發到對方，使用了優化方法（Nagle算法），將多次間隔較小且數據量小的數據，合并成一個大的數據塊，然后進行封包。這樣，接收端，就難于分辨出來了，必須提供科學的拆包機制。
對于UDP，不會使用塊的合并優化算法，這樣，實際上目前認為，是由于UDP支持的是一對多的模式，所以接收端的skbuff(套接字緩沖區）采用了鏈式結構來記錄每一個到達的UDP包，在每個UDP包中就有了消息頭（消息來源地址，端口等信息），這樣，對于接收端來說，就容易進行區分處理了

保護消息邊界和流

那么什么是保護消息邊界和流呢?

保護消息邊界，就是指傳輸協議把數據當作一條獨立的消息在網上
傳輸,接收端只能接收獨立的消息.也就是說存在保護消息邊界,接收
端一次只能接收發送端發出的一個數據包.
而面向流則是指無保護消息保護邊界的,如果發送端連續發送數據,
接收端有可能在一次接收動作中,會接收兩個或者更多的數據包.

我們舉個例子來說,例如,我們連續發送三個數據包,大小分別是2k,
4k , 8k,這三個數據包,都已經到達了接收端的網絡堆棧中,如果使
用UDP協議,不管我們使用多大的接收緩沖區去接收數據,我們必須有
三次接收動作,才能夠把所有的數據包接收完.而使用TCP協議,我們
只要把接收的緩沖區大小設置在14k以上,我們就能夠一次把所有的
數據包接收下來.只需要有一次接收動作.

這就是因為UDP協議的保護消息邊界使得每一個消息都是獨立的.而
流傳輸,卻把數據當作一串數據流,他不認為數據是一個一個的消息.

所以有很多人在使用tcp協議通訊的時候,并不清楚tcp是基于流的
傳輸,當連續發送數據的時候,他們時常會認識tcp會丟包.其實不然,
因為當他們使用的緩沖區足夠大時,他們有可能會一次接收到兩個甚
至更多的數據包,而很多人往往會忽視這一點,只解析檢查了第一個
數據包,而已經接收的其他數據包卻被忽略了.所以大家如果要作這
類的網絡編程的時候,必須要注意這一點.

結論：
根據以上所說，可以這樣理解，TCP為了保證可靠傳輸，盡量減少額外
開銷（每次發包都要驗證），因此采用了流式傳輸，面向流的傳輸，
相對于面向消息的傳輸，可以減少發送包的數量。從而減少了額外開
銷。但是，對于數據傳輸頻繁的程序來講，使用TCP可能會容易粘包。
當然，對接收端的程序來講，如果機器負荷很重，也會在接收緩沖里
粘包。這樣，就需要接收端額外拆包，增加了工作量。因此，這個特
別適合的是數據要求可靠傳輸，但是不需要太頻繁傳輸的場合（
兩次操作間隔100ms，具體是由TCP等待發送間隔決定的，取決于內核
中的socket的寫法）

而UDP，由于面向的是消息傳輸，它把所有接收到的消息都掛接到緩沖
區的接受隊列中，因此，它對于數據的提取分離就更加方便，但是，
它沒有粘包機制，因此，當發送數據量較小的時候，就會發生數據包
有效載荷較小的情況，也會增加多次發送的系統發送開銷（系統調用，
寫硬件等）和接收開銷。因此，應該最好設置一個比較合適的數據包
的包長，來進行UDP數據的發送。（UDP最大載荷為1472，因此最好能
每次傳輸接近這個數的數據量，這特別適合于視頻，音頻等大塊數據
的發送，同時，通過減少握手來保證流媒體的實時性）

來自: http://hi.baidu.com/chongerfeia/blog/item/b1e572f631dd7e28bd310965.html

TCP無保護消息邊界的解決
針對這個問題，一般有3種解決方案：

(1)發送固定長度的消息

(2)把消息的尺寸與消息一塊發送

(3)使用特殊標記來區分消息間隔

下面我們主要分析下前兩種方法：

1、發送固定長度的消息
這種方法的好處是他非常容易，而且只要指定好消息的長度，沒有遺漏未未發的數據，我們重寫了一個SendMessage方法。代碼如下：

private static int SendMessage(Socket s, byte[] msg)

        {
            int offset = 0;
            int size = msg.Length;
            int dataleft = size;

while (dataleft > 0)
{

                int sent = s.Send(msg, offset, SocketFlags.None);
                offset += sent;
                dataleft -= sent;

}

return offset;
}

簡要分析一下這個函數：形參s是進行通信的套接字，msg即待發送的字節數組。該方法使用while循環檢查是否還有數據未發送，尤其當發送一個很龐大的數據包，在不能一次性發完的情況下作用比較明顯。特別的，用sent來記錄實際發送的數據量，和recv是異曲同工的作用，最后返回發送的實際數據總數。

有sentMessage函數后，還要根據指定的消息長度來設計一個新的Recive方法。代碼如下：

private byte[] ReciveMessage(Socket s, int size)
{

            int offset = 0;
            int recv;
            int dataleft = size;
            byte[] msg = new byte[size];

            while (dataleft > 0)
            {
                //接收消息
                recv = s.Receive(msg, offset, dataleft, 0);
                if (recv == 0)
                {
                    break;
                }
                offset += recv;
                dataleft -= recv;
            }
            return msg;
        }
以上這種做法比較適合于消息長度不是很長的情況。
2、消息長度與消息一同發送
我們可以這樣做：通過使用消息的整形數值來表示消息的實際大小，所以要把整形數轉換為字節類型。下面是發送變長消息的SendMessage方法。具體代碼如下：
private static int SendMessage(Socket s, byte[] msg)
        {
            int offset = 0;
            int sent;
            int size = msg.Length;
            int dataleft = size;
            byte[] msgsize = new byte[2];
            //將消息尺寸從整形轉換成可以發送的字節型
            msgsize = BitConverter.GetBytes(size);

            //發送消息的長度信息
            sent = s.Send(size);
            while (dataleft > 0)
            {
                sent = s.Send(msg, offset, dataleft, SocketFlags.None);
                //設置偏移量
                offset += sent;
                dataleft -= sent;
            }
            return offset;
        }

下面是接收變長消息的ReciveVarMessage方法。代碼如下：
private byte[] ReciveVarMessage(Socket s)
        {

            int offset = 0;
            int recv;
            byte[] msgsize = new byte[2];

            //將字節數組的消息長度信息轉換為整形
            int size = BitConverter.ToInt16(msgsize);
            int dataleft = size;
            byte[] msg = new byte[size];

            //接收2個字節大小的長度信息
            recv = s.Receive(msgsize, 0, 2, 0);
            while (dataleft > 0)
            {
                //接收數據
                recv = s.Receive(msg, offset, dataleft, 0);
                if (recv == 0)
                {
                    break;
                }
                offset += recv;
                dataleft -= recv;
            }
            return msg;
        }

posted @ 2011-09-01 18:36 simplyzhao 閱讀(661) | 評論 (0) | 編輯收藏

2011字符串-最長重復子串，后綴數組

from: Programming Pearl

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* longdup.c -- Print longest string duplicated M times */

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

int pstrcmp(char **p, char **q)
{   return strcmp(*p, *q); }

int comlen(char *p, char *q)
{    int i = 0;
    while (*p && (*p++ == *q++))
        i++;
    return i;
}

#define M 1
#define MAXN 5000000
char c[MAXN], *a[MAXN];

int main()
{   int i, ch, n = 0, maxi, maxlen = -1;
    while ((ch = getchar()) != EOF) {
        a[n] = &c[n];
        c[n++] = ch;
    }
    c[n] = 0;
    qsort(a, n, sizeof(char *), pstrcmp);
    for (i = 0; i < n-M; i++)
        if (comlen(a[i], a[i+M]) > maxlen) {
            maxlen = comlen(a[i], a[i+M]);
            maxi = i;
        }
    printf("%.*s\n", maxlen, a[maxi]);
    return 0;
}

posted @ 2011-08-19 15:11 simplyzhao 閱讀(599) | 評論 (1) | 編輯收藏

2011字符串哈希，統計詞頻（from 編程珠璣）

代碼1（STL的map版本）

#include<iostream>
#include<map>
#include<string>

using namespace std;

int
main(int argc, char **argv)
{
    map<string, int> M;
    map<string, int>::iterator j;
    string t;
    while(cin>>t)
        M[t]++;

    for(j=M.begin(); j!=M.end(); ++j)
        cout<<j->first<<"\t"<<j->second<<endl;

    return 0;
}

代碼2（自己的Hash）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define WORD_BUF 128
#define NHASH 29989 /* prime number just bigger than needed */
#define MULT 31

struct HNode {
    char *word;
    int count;
    struct HNode *next;
};
struct HNode *Hash[NHASH] = {NULL};

#define NODEGROUP 1000
struct HNode *nodebuf;
int nodeleft = 0;

struct HNode *
node_alloc()
{
    if(nodeleft == 0) {
        nodebuf = (struct HNode *)malloc(NODEGROUP * sizeof(struct HNode));
        nodeleft = NODEGROUP;
    }
    --nodeleft;
    return (nodebuf++);
}

unsigned int
hash(char *str) /* a simple implementation of string-hash, others like ELFHash

*/
{
    unsigned int ret = 0;
    char *ptr;
    for(ptr=str; *ptr; ++ptr)
        ret = ret * MULT + (*ptr);
    return (ret % NHASH);
}

void
insert_hash(char *word)
{
    struct HNode *node;
    unsigned int h = hash(word);
    for(node=Hash[h]; node!=NULL; node=node->next)
        if(strcmp(node->word, word) == 0) {
            ++(node->count);
            return;
        }
    struct HNode *pend = node_alloc();
    pend->word = strdup(word);
    pend->count = 1;
    pend->next = Hash[h];
    Hash[h] = pend;
}

int
main(int argc, char **argv)
{
    char buf[WORD_BUF];
    while(scanf("%s", buf) != EOF) {
        insert_hash(buf);
    }

    int i;
    struct HNode *node;
    for(i=0; i<NHASH; ++i)
        for(node=Hash[i]; node!=NULL; node=node->next)
            printf("%s\t%d\n", node->word, node->count);

    return 0;
}

posted @ 2011-08-19 14:37 simplyzhao 閱讀(591) | 評論 (0) | 編輯收藏

2011趣題-尋找除法的循環節

代碼:

/* 問題: 兩整數相除，求循環節 */
/* 分析:
* 模擬整數相除的步驟，記錄每次的商、余，當余重復時即發現循環節
* 余的范圍為[0, 被除數)，因此記錄數組的大小可根據被除數確定
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void
get_circle_digits(unsigned int a, unsigned int b)
{
    int i, mod, tmp, index = 0;
    int *div = (int *)malloc(sizeof(int) * b);
    int *mod_pos = (int *)malloc(sizeof(int) * b);
    memset(mod_pos, -1, sizeof(int)*b);
    mod = a = a%b;
    while(1) {
        if(mod==0 || mod_pos[mod]!=-1)
            break;
        mod_pos[mod] = index;
        tmp = mod*10;
        div[index] = tmp / b;
        mod = tmp % b;
        ++index;
    }
    if(mod == 0)
        printf("No Circle\n");
    else {
        printf("0.");
        for(i=0; i<mod_pos[mod]; i++)
            printf("%d", div[i]);
        printf("(");
        for(i=mod_pos[mod]; i<index; i++)
            printf("%d", div[i]);
        printf(")");
        printf("\n");
    }
}

int
main(int argc, char **argv)
{
    unsigned int a, b;
    while(scanf("%u %u", &a, &b) != EOF) {
        get_circle_digits(a, b);
    }
    return 0;
}

posted @ 2011-08-17 16:24 simplyzhao 閱讀(493) | 評論 (0) | 編輯收藏

2011搜索-題，DFS，沿路徑搜索

代碼:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_K 101
#define MAX_N 1001
char matrix[MAX_N][MAX_N];
char visited[MAX_N];
short count[MAX_N];
int pastures[MAX_K];

int K, N, M;

void
dfs(int pasture)
{
    int i;
    ++count[pasture];
    visited[pasture] = 1;
    for(i=1; i<=N; ++i) {
        if(matrix[pasture][i] && !visited[i])
            dfs(i);
    }
}

int
main(int argc, char **argv)
{
    int i, x, y, ret = 0;
    scanf("%d %d %d", &K, &N, &M);
    for(i=1; i<=K; ++i)
        scanf("%d", pastures+i);
    for(i=1; i<=M; ++i) {
        scanf("%d %d", &x, &y);
        matrix[x][y] = 1;
    }

    for(i=1; i<=K; ++i) {
        memset(visited, 0, sizeof(visited));
        dfs(pastures[i]);
    }

    for(i=1; i<=N; ++i)
        if(count[i] == K)
            ++ret;
    printf("%d\n", ret);
}

Cow Picnic

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 3878		Accepted: 1576

Description

The cows are having a picnic! Each of Farmer John's K (1 ≤ K ≤ 100) cows is grazing in one of N (1 ≤ N ≤ 1,000) pastures, conveniently numbered 1...N. The pastures are connected by M (1 ≤ M ≤ 10,000) one-way paths (no path connects a pasture to itself).

The cows want to gather in the same pasture for their picnic, but (because of the one-way paths) some cows may only be able to get to some pastures. Help the cows out by figuring out how many pastures are reachable by all cows, and hence are possible picnic locations.

Input

Line 1: Three space-separated integers, respectively: K, N, and M
Lines 2..K+1: Line i+1 contains a single integer (1..N) which is the number of the pasture in which cow i is grazing.
Lines K+2..M+K+1: Each line contains two space-separated integers, respectively A and B (both 1..N and A != B), representing a one-way path from pasture A to pasture B.

Output

Line 1: The single integer that is the number of pastures that are reachable by all cows via the one-way paths.

Sample Input

Sample Output

Hint

The cows can meet in pastures 3 or 4.

Source

USACO 2006 December Silver

posted @ 2011-08-15 16:13 simplyzhao 閱讀(214) | 評論 (0) | 編輯收藏

2011搜索-題，DFS，圖著色

代碼:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#define MAX_NUM 26
char adj[MAX_NUM][MAX_NUM];
int num, ret, colors[MAX_NUM];

int
is_valid(int depth, int color)
{
    int i;
    for(i=0; i<depth; ++i) {
        if(adj[i][depth] && colors[i]==color)
            return 0;
    }
    return 1;
}

void
dfs(int depth, int color_used)
{
    if(color_used >= ret)
        return;
    if(depth >= num) {
        ret = color_used;
        return;
    }

    int i;
    for(i=0; i<color_used; ++i) {
        if(is_valid(depth, i)) {
            colors[depth] = i;
            dfs(depth+1, color_used);
            colors[depth] = -1;
        }
    }
    colors[depth] = color_used;
    dfs(depth+1, color_used+1);
    colors[depth] = -1;
}

int
main(int argc, char **argv)
{
    int i;
    char info[MAX_NUM+2], *ptr;

    while(scanf("%d", &num)!=EOF && num) {
        ret = INT_MAX;
        memset(colors, -1, sizeof(colors));
        memset(adj, 0, sizeof(adj));
        for(i=0; i<num; ++i) {
            scanf("%s", info);
            ptr = info+2;
            while(*ptr != '\0') {
                adj[i][(*ptr)-'A'] = 1;
                ++ptr;
            }
        }
        dfs(0, 0);
        printf("%d %s needed.\n", ret, ret<=1?"channel":"channels");
    }
}

Channel Allocation

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 8353		Accepted: 4248

Description

When a radio station is broadcasting over a very large area, repeaters are used to retransmit the signal so that every receiver has a strong signal. However, the channels used by each repeater must be carefully chosen so that nearby repeaters do not interfere with one another. This condition is satisfied if adjacent repeaters use different channels.

Since the radio frequency spectrum is a precious resource, the number of channels required by a given network of repeaters should be minimised. You have to write a program that reads in a description of a repeater network and determines the minimum number of channels required.

Input

The input consists of a number of maps of repeater networks. Each map begins with a line containing the number of repeaters. This is between 1 and 26, and the repeaters are referred to by consecutive upper-case letters of the alphabet starting with A. For example, ten repeaters would have the names A,B,C,...,I and J. A network with zero repeaters indicates the end of input.

Following the number of repeaters is a list of adjacency relationships. Each line has the form:

A:BCDH

which indicates that the repeaters B, C, D and H are adjacent to the repeater A. The first line describes those adjacent to repeater A, the second those adjacent to B, and so on for all of the repeaters. If a repeater is not adjacent to any other, its line has the form

A:

The repeaters are listed in alphabetical order.

Note that the adjacency is a symmetric relationship; if A is adjacent to B, then B is necessarily adjacent to A. Also, since the repeaters lie in a plane, the graph formed by connecting adjacent repeaters does not have any line segments that cross.

Output

For each map (except the final one with no repeaters), print a line containing the minumum number of channels needed so that no adjacent channels interfere. The sample output shows the format of this line. Take care that channels is in the singular form when only one channel is required.

Sample Input

2
A:
B:
4
A:BC
B:ACD
C:ABD
D:BC
4
A:BCD
B:ACD
C:ABD
D:ABC
0

Sample Output

1 channel needed.
3 channels needed.
4 channels needed.

Source

Southern African 2001

posted @ 2011-08-14 10:32 simplyzhao 閱讀(292) | 評論 (0) | 編輯收藏

2011搜索-題，DFS，類似計算連通區域的個數

代碼:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_NUM 100
#define VALID(x, y) ((x)>=0 && (x)<m && (y)>=0 && (y)<n)
int m, n, count;
char grid[MAX_NUM][MAX_NUM+1];
char visited[MAX_NUM][MAX_NUM+1];

const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
void
dfs_inner(int x, int y)
{
    int i, next_x, next_y;
    visited[x][y] = 1;
    for(i=0; i<8; ++i) {
        next_x = x + dx[i];
        next_y = y + dy[i];
        if(VALID(next_x, next_y) && !visited[next_x][next_y] &&
                grid[next_x][next_y]=='@')
            dfs_inner(next_x, next_y);
    }
}

void
dfs()
{
    int i, j;
    for(i=0; i<m; ++i)
        for(j=0; j<n; ++j)
            if(!visited[i][j] && grid[i][j]=='@') {
                ++count;
                dfs_inner(i, j);
            }
}

int
main(int argc, char **argv)
{
    int i;
    while(scanf("%d %d", &m, &n)!= EOF && m) {
        count = 0;
        memset(visited, 0, sizeof(visited));
        for(i=0; i<m; ++i)
            scanf("%s", grid[i]);
        dfs();
        printf("%d\n", count);
    }
}

Oil Deposits

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 7595		Accepted: 4267

Description

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

Input

The input contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*', representing the absence of oil, or `@', representing an oil pocket.

Output

are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

Sample Input

1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5  ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0

Sample Output

0 1 2 2

Source

Mid-Central USA 1997

posted @ 2011-08-14 10:29 simplyzhao 閱讀(337) | 評論 (0) | 編輯收藏

2011搜索-題，BFS and DFS

摘要: 題目:
給你一個3升的杯子和一個5升的(杯子是沒有刻度的)，要你取4升水來(水可以無限取)，請問該如何操作。
泛化:
給你一個m升的杯子和一個n升的(杯子是沒有刻度的)，要你取target升水來（水可以無限?。?，請問該如何操作.

思路:
搜索: BFS or DFS 閱讀全文

posted @ 2011-08-12 17:40 simplyzhao 閱讀(211) | 評論 (0) | 編輯收藏

2011搜索-二分搜索

前提: 已排序
時間復雜度: O(logN)
例如: 找出某個target出現的位置（隨機），某個target第一次出現的位置，某個target最后一次出現的位置

問題: 如果在未排序的數組中使用二分搜索，結果會怎么樣？

答: 如果二分搜索聲稱找到了target，那么該target就一定存在于數組中，
但是，在應用于未排序數組時，算法有時會在target實際存在的情況下報告說該target不存在

代碼:

int
vector_bsearch(struct Vector *vector, const void *target, compare_func compare)
{
    int lo, hi, mid, tmp;
    lo = 0;
    hi = (vector->count) - 1;
    while(lo <= hi) {
        mid = lo + ((hi - lo) >> 1);
        tmp = compare(vector->array[mid], target);
        if(tmp == 0)
            return mid;
        else if(tmp > 0)
            hi = mid - 1;
        else
            lo = mid + 1;
    }
    return -1;
}

int
vector_lower(struct Vector *vector, const void *target, compare_func compare)
{
    int lo, hi, mid;
    lo = -1;
    hi = vector->count;
    /* distance between lo and hi at least larger than 1, which ensure mid won't equals to either lo or hi */
    while(lo+1 != hi) {
        /* loop invariant: vector[lo]<target && vector[hi]>=target && lo<hi */
        mid = lo + ((hi - lo) >> 1);
        if(compare(vector->array[mid], target) >= 0)
            hi = mid;
        else
            lo = mid;
    }
    if(hi>=(vector->count) || compare(vector->array[hi], target)!=0)
        return -1;
    return hi;
}

int
vector_upper(struct Vector *vector, const void *target, compare_func compare)
{
    int lo, hi, mid;
    lo = -1;
    hi = vector->count;
    /* distance between lo and hi at least larger than 1, which ensure mid won't equals to either lo or hi */
    while(lo+1 != hi) {
        /* loop invariant: vector[lo]<=target && vector[hi]>target && lo<hi */
        mid = lo + ((hi - lo) >> 1);
        if(compare(vector->array[mid], target) <= 0)
            lo = mid;
        else
            hi = mid;
    }
    if(lo<0 || compare(vector->array[lo], target)!=0)
        return -1;
    return lo;
}

posted @ 2011-08-12 17:19 simplyzhao 閱讀(192) | 評論 (0) | 編輯收藏

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

A Za, A Za, Fighting...

導航

統計

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜