A Za, A Za, Fighting...

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 阅读(1106) | 评论 (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 阅读(602) | 评论 (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 阅读(559) | 评论 (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 阅读(549) | 评论 (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 阅读(460) | 评论 (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 阅读(179) | 评论 (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 阅读(251) | 评论 (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 阅读(301) | 评论 (0) | 编辑收藏

2011搜索-题，BFS and DFS

摘要: 题目:
给你一个3升的杯子和一个5升的(杯子是没有刻度的)，要你取4升水来(水可以无限取)，请问该如何操作。
泛化:
给你一个m升的杯子和一个n升的(杯子是没有刻度的)，要你取target升水来（水可以无限取），请问该如何操作.

思路:
搜索: BFS or DFS 阅读全文

posted @ 2011-08-12 17:40 simplyzhao 阅读(192) | 评论 (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 阅读(156) | 评论 (0) | 编辑收藏

A Za, A Za, Fighting...

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜