题意 给你农场的邻接矩阵 求连通所有农场的最小消耗

和上一题一样裸的最小生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 105, M = 10050;
int par[N], ans, n, m, t;
struct edge { int u, v, w;} e[M];
bool cmp(edge a, edge b){ return a.w < b.w;}

int Find(int x)
{
    int r = x, tmp;
    while(par[r] >= 0) r = par[r];
    while(x != r)
    {
        tmp = par[x];
        par[x] = r;
        x = tmp;
    }
    return r;
}

void Union(int u, int v)
{
    int ru = Find(u), rv = Find(v), tmp = par[ru] + par[rv];
    if(par[ru] < par[rv])
        par[rv] = ru, par[ru] = tmp;
    else
        par[ru] = rv, par[rv] = tmp;
}

void kruskal()
{
    int cur = 0, u, v;
    memset(par, -1, sizeof(par));
    for(int i = 1; i <= m; ++i)
    {
        u = e[i].u, v = e[i].v;
        if(Find(u) != Find(v))
        {
            ans += e[i].w;
            Union(u, v);
            ++cur;
        }
        if(cur >= n - 1) break;
    }
}

int main()
{
    while(~scanf("%d", &n))
    {
        ans = m = 0;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                scanf("%d", &t);
                if(j < i) e[++m].u = i, e[m].v = j, e[m].w = t;
            }
        }
        sort(e + 1, e + m + 1, cmp);
        kruskal();
        printf("%d\n", ans);
    }
    return 0;
}

Agri-Net

Description
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.

Input

The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.

Output

For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.

Sample Input

4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0

Sample Output

28

题意 给你n个点的坐标 每个点都可与其它n-1个点相连 求这n个点的最小生成树的权重

裸的最小生成树 直接kruskal咯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 105, M = 10050;
double x[N], y[N], ans;
int n, m , par[N];

struct edge {
    int u, v;
    double w;
} e[M];

bool cmp(edge a, edge b)  { return a.w < b.w;}

int Find(int x)
{
    int r = x;
    while(par[r] >= 0) r = par[r];
    while(x != r) //压缩
    {
        int tmp = par[x];
        par[x] = r;
        x = tmp;
    }
    return r;
}

void Union(int u, int v)
{
    int ru = Find(u), rv = Find(v), tmp = par[ru] + par[rv];
    if(par[ru] > par[rv])
        par[ru] = rv, par[rv] = tmp;
    else
        par[rv] = ru, par[ru] = tmp;
}

void kruskal()
{
    int cur = 0, u, v;
    memset(par, -1, sizeof(par)); //初始化并查集
    for(int i = 1; i <= m; ++i)
    {
        u = e[i].u, v = e[i].v;
        if(Find(u) != Find(v))
        {
            ans += e[i].w;
            ++cur;
            Union(u, v);
        }
        if(cur >= n - 1) break;
    }
}

int main()
{
    int cas = 0;
    while(scanf("%d", &n), n)
    {
        if(cas) printf("\n");
        m = 0;

        for(int i = 1; i <= n; ++i)
        {
            scanf("%lf%lf", &x[i], &y[i]);
            for(int j = 1; j < i; ++j)
            {
                double dis = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
                e[++m].u = i, e[m].v = j, e[m].w = dis;
            }
        }

        sort(e + 1, e + 1 + m, cmp);
        ans = 0; kruskal();
        printf("Case #%d:\nThe minimal distance is: %.2f\n", ++cas, ans);
    }

    return 0;
}

Swordfish Time Limit:2 Seconds Memory Limit:65536 KB There exists a world within our world
A world beneath what we call cyberspace.
A world protected by firewalls,
passwords and the most advanced
security systems.
In this world we hide
our deepest secrets,
our most incriminating information,
and of course, a shole lot of money.
This is the world of Swordfish.
We all remember that in the movie Swordfish, Gabriel broke into the World Bank Investors Group in West Los Angeles, to rob $9.5 billion. And he needed Stanley, the best hacker in the world, to help him break into the password protecting the bank system. Stanley’s lovely daughter Holly was seized by Gabriel, so he had to work for him. But at the last moment, Stanley made some little trick in his hacker mission: he injected a trojan horse in the bank system, so the money would jump from one account to another account every 60 seconds, and would continue jumping in the next 10 years. Only Stanley knew when and where to get the money. If Gabriel killed Stanley, he would never get a single dollar. Stanley wanted Gabriel to release all these hostages and he would help him to find the money back.
You who has watched the movie know that Gabriel at last got the money by threatening to hang Ginger to death. Why not Gabriel go get the money himself? Because these money keep jumping, and these accounts are scattered in different cities. In order to gather up these money Gabriel would need to build money transfering tunnels to connect all these cities. Surely it will be really expensive to construct such a transfering tunnel, so Gabriel wants to find out the minimal total length of the tunnel required to connect all these cites. Now he asks you to write a computer program to find out the minimal length. Since Gabriel will get caught at the end of it anyway, so you can go ahead and write the program without feeling guilty about helping a criminal.
Input:
The input contains several test cases. Each test case begins with a line contains only one integer N (0 <= N <=100), which indicates the number of cities you have to connect. The next N lines each contains two real numbers X and Y(-10000 <= X,Y <= 10000), which are the citie’s Cartesian coordinates (to make the problem simple, we can assume that we live in a flat world). The input is terminated by a case with N=0 and you must not print any output for this case.
Output:
You need to help Gabriel calculate the minimal length of tunnel needed to connect all these cites. You can saftly assume that such a tunnel can be built directly from one city to another. For each of the input cases, the output shall consist of two lines: the first line contains “Case /#n:”, where n is the case number (starting from 1); and the next line contains “The minimal distance is: d”, where d is the minimal distance, rounded to 2 decimal places. Output a blank line between two test cases.
Sample Input:
5 0 0 0 1 1 1 1 0 0.5 0.5 0 Sample Output:
Case /#1: The minimal distance is: 2.83

题意 在所有城市中找一个中心满足这个中心到所有公交站点距离的最大值最小 输出最小距离和满足最小距离编号最小的中心

最基础的BFS 对每个公交站点BFS dis[i]表示编号为i的点到所有公交站点距离的最大值 bfs完所有站点后 dis[i]最小的点就是要求的点咯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
using namespace std;

typedef set<int>::iterator it;
const int N = 10000;
int dis[N], tdis[N], link[N][12];
queue<int> q;
set<int> zone;

void bfs(int o)
{
    memset(tdis, 0, sizeof(tdis));
    tdis[o] = 1;
    q.push(o);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        if(tdis[cur] > dis[cur]) dis[cur] = tdis[cur];
        for(int i = 1; i <= link[cur][0]; ++i)
        {
            int j = link[cur][i];
            if(tdis[j] == 0)  q.push(j), tdis[j] = tdis[cur] + 1;
        }
    }
}

int main()
{
    int cas, nz, nr, id, mz, mr, ans, t;
    scanf("%d", &cas);
    while(cas--)
    {
        zone.clear();
        memset(dis, 0, sizeof(dis));
        scanf("%d%d", &nz, &nr);
        for(int i = 1; i <= nz; ++i)
        {
            scanf("%d %d", &id, &mz);
            link[id][0] = mz;
            zone.insert(id);
            for(int i = 1; i <= mz; ++i)
                scanf("%d", &link[id][i]);
        }

        for(int i = 1; i <= nr; ++i)
        {
            scanf("%d", &mr);
            for(int j = 1; j <= mr; ++j)
            {
                scanf("%d", &t);
                bfs(t);
            }
        }

        it i = zone.begin();
        ans = *i;
        for(++i; i != zone.end(); ++i)
            if(dis[*i] < dis[ans]) ans = *i;
        printf("%d %d\n", dis[ans], ans);
    }
    return 0;
}

Bus Pass Time Limit:5 Seconds Memory Limit:32768 KB

You travel a lot by bus and the costs of all the seperate tickets are starting to add up.

Therefore you want to see if it might be advantageous for you to buy a bus pass.

The way the bus system works in your country (and also in the Netherlands) is as follows:

when you buy a bus pass, you have to indicate a center zone and a star value. You are allowed to travel freely in any zone which has a distance to your center zone which is less than your star value. For example, if you have a star value of one, you can only travel in your center zone. If you have a star value of two, you can also travel in all adjacent zones, et cetera.

You have a list of all bus trips you frequently make, and would like to determine the minimum star value you need to make all these trips using your buss pass. But this is not always an easy task. For example look at the following figure:

Here you want to be able to travel from A to B and from B to D. The best center zone is 7400, for which you only need a star value of 4. Note that you do not even visit this zone on your trips!

Input

On the first line an integert(1 <=t<= 100): the number of test cases. Then for each test case:

One line with two integersnz(2 <=nz<= 9 999) andnr(1 <=nr<= 10): the number of zones and the number of bus trips, respectively.

nz lines starting with two integers idi (1 <= idi <= 9 999) and mzi (1 <= mzi <= 10), a number identifying the i-th zone and the number of zones adjacent to it, followed by mzi integers: the numbers of the adjacent zones.

nr lines starting with one integer mri (1 <= mri <= 20), indicating the number of zones the ith bus trip visits, followed by mri integers: the numbers of the zones through which the bus passes in the order in which they are visited.

All zones are connected, either directly or via other zones.

Output

For each test case:

One line with two integers, the minimum star value and the id of a center zone which achieves this minimum star value. If there are multiple possibilities, choose the zone with the lowest number.

Sample Input

1
17 2
7400 6 7401 7402 7403 7404 7405 7406
7401 6 7412 7402 7400 7406 7410 7411
7402 5 7412 7403 7400 7401 7411
7403 6 7413 7414 7404 7400 7402 7412
7404 5 7403 7414 7415 7405 7400
7405 6 7404 7415 7407 7408 7406 7400
7406 7 7400 7405 7407 7408 7409 7410 7401
7407 4 7408 7406 7405 7415
7408 4 7409 7406 7405 7407
7409 3 7410 7406 7408
7410 4 7411 7401 7406 7409
7411 5 7416 7412 7402 7401 7410
7412 6 7416 7411 7401 7402 7403 7413
7413 3 7412 7403 7414
7414 3 7413 7403 7404
7415 3 7404 7405 7407
7416 2 7411 7412
5 7409 7408 7407 7405 7415
6 7415 7404 7414 7413 7412 7416

Sample Output

4 7400

题意 求迷宫中从a的位置到r的位置需要的最少时间 经过’.’方格需要1s 经过‘x’方格需要两秒 ‘/#’表示墙

由于有1s和2s两种情况 需要在基础迷宫bfs上加些判断

令到达每个点的时间初始为无穷大 当从一个点到达该点用的时间比他本来的时间小时 更新这个点的时间并将这个点入队 扫描完全图就得到答案咯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int N = 205;
char mat[N][N];
int time[N][N], sx, sy;
int dx[4] = {0, 0, -1, 1};
int dy[4] = { -1, 1, 0, 0};
struct grid
{
    int x, y;
    grid(int xx = 0, int yy = 0): x(xx), y(yy) {}
};

void bfs()
{
    memset(time, 0x3f, sizeof(time));
    time[sx][sy] = 0;
    queue<grid> g;
    g.push(grid(sx, sy));

    while(!g.empty())
    {
        grid cur = g.front();
        g.pop();
        int cx = cur.x, cy = cur.y, ct = time[cx][cy];
        for(int i = 0; i < 4; ++i)
        {
            int nx = cx + dx[i], ny = cy + dy[i];
            if(mat[nx][ny] && mat[nx][ny] != '#')
            {
                int tt = ct + 1;
                if(mat[cx][cy] == 'x') ++tt;
                if(tt < time[nx][ny])
                {
                    time[nx][ny] = tt;
                    g.push(grid(nx, ny));
                }
            }
        }
    }
}

int main()
{
    int n, m, ex, ey;
    while (~scanf("%d%d", &n, &m))
    {
        memset(mat, 0, sizeof(mat));
        for(int i = 1; i <= n; ++i)
            scanf("%s", mat[i] + 1);
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                if(mat[i][j] == 'a') sx = i, sy = j;
                else if(mat[i][j] == 'r') ex = i, ey = j;
        bfs();
        if(time[ex][ey] != time[0][0])
            printf("%d\n", time[ex][ey]);
        else
            printf("Poor ANGEL has to stay in the prison all his life.\n");
    }

    return 0;
}

题意 求矩阵中包含‘@’的’.’连通块中元素数量 ‘@’也看做’.’

最基础的dfs了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 30;
char mat[N][N];
int dx[4] = {0, 0, -1, 1}, dy[4] = { -1, 1, 0, 0};
int ans;

void dfs(int r, int c)
{
    if(mat[r][c] != '.') return;
    mat[r][c] = '#';
    for(int i = 0; i < 4; ++i)
    {
        int x = r + dx[i], y = c + dy[i];
        if(mat[x][y] == '.')
        {
            dfs(x, y);
            ++ans;
        }
    }
}

int main()
{
    int m, n, sx, sy;
    while(scanf("%d%d", &m, &n), m)
    {
        memset(mat, 0, sizeof(mat));
        for(int i = 1; i <= n; ++i)
            scanf("%s", mat[i] + 1);
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                if(mat[i][j] == '@') sx = i, sy = j;
        ans = 1;
        dfs(sx, sy);
        printf("%d\n", ans);
    }
}

Red and Black

Description
There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.
Write a program to count the number of black tiles which he can reach by repeating the moves described above.

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.
There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.
‘.’ - a black tile
‘/#’ - a red tile
‘@’ - a man on a black tile(appears exactly once in a data set)
The end of the input is indicated by a line consisting of two zeros.

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample Input

6 9 …./#. …../# …… …… …… …… …… /#@…/# ./#../#. 11 9 ./#……… ./#./#/#/#/#/#/#/#. ./#./#…../#. ./#./#./#/#/#./#. ./#./#..@/#./#. ./#./#/#/#/#/#./#. ./#……./#. ./#/#/#/#/#/#/#/#/#. ……….. 11 6 ../#../#../#.. ../#../#../#.. ../#../#../#/#/# ../#../#../#@. ../#../#../#.. ../#../#../#.. 7 7 ../#./#.. ../#./#.. /#/#/#./#/#/# ...@… /#/#/#./#/#/# ../#./#.. ../#./#.. 0 0

Sample Output

45 59 6 13

题意 两块农田里面的管道可以直接连接的话 他们就可以共用一个水源 有11种农田 上面的管道位置是一定的 给你一个农田矩阵 问至少需要多少水源

DFS的连通块问题 两个相邻农田的管道可以直接连接的话他们就属于一个连通块 题目就是求连通块个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 55;
char mat[N][N];
int type[11][4] = {   //对应11种水管类型 按顺时针方向有管道的为1否则为0
    {1, 0, 0, 1}, {1, 1, 0, 0}, {0, 0, 1, 1}, {0, 1, 1, 0},
    {1, 0, 1, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}, {1, 0, 1, 1},
    {0, 1, 1, 1}, {1, 1, 1, 0}, {1, 1, 1, 1}
};

int dfs(int r, int c)
{
    int cur = mat[r][c] - 'A';
    if(cur < 0 || cur > 10) return 0;
    mat[r][c] = 0;           //标记已经访问 0-'A'是小于0的
    int up = mat[r - 1][c] - 'A', dw = mat[r + 1][c] - 'A',
        le = mat[r][c - 1] - 'A', ri = mat[r][c + 1] - 'A';  //4个相邻块的管道类型
    if(up > -1 && up < 11 && type[up][2] && type[cur][0])  dfs(r - 1, c);
    if(dw > -1 && dw < 11 && type[dw][0] && type[cur][2])  dfs(r + 1, c);
    if(le > -1 && le < 11 && type[le][1] && type[cur][3])  dfs(r, c - 1);
    if(ri > -1 && ri < 11 && type[ri][3] && type[cur][1])  dfs(r, c + 1);
    return 1;     //一个连通块中只有一个返回1
}

int main()
{
    int n, m, ans;
    while (scanf("%d%d", &n, &m), n >= 0)
    {
        ans = 0;
        memset(mat, 0, sizeof(mat));
        for(int i = 1; i <= n; ++i)
            scanf("%s", mat[i] + 1);
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                ans += dfs(i, j);
        printf("%d\n", ans);
    }
    return 0;
}

Farm Irrigation Time Limit:2 Seconds Memory Limit:65536 KB

Benny has a spacious farm land to irrigate. The farm land is a rectangle, and is divided into a lot of samll squares. Water pipes are placed in these squares. Different square has a different type of pipe. There are 11 types of pipes, which is marked from A to K, as Figure 1 shows.

Figure 1

Benny has a map of his farm, which is an array of marks denoting the distribution of water pipes over the whole farm. For example, if he has a map

ADC FJK IHE then the water pipes are distributed like
Figure 2

Several wellsprings are found in the center of some squares, so water can flow along the pipes from one square to another. If water flow crosses one square, the whole farm land in this square is irrigated and will have a good harvest in autumn.

Now Benny wants to know at least how many wellsprings should be found to have the whole farm land irrigated. Can you help him?

Note: In the above example, at least 3 wellsprings are needed, as those red points in Figure 2 show.
Input

There are several test cases! In each test case, the first line contains 2 integers M and N, then M lines follow. In each of these lines, there are N characters, in the range of ‘A’ to ‘K’, denoting the type of water pipe over the corresponding square. A negative M or N denotes the end of input, else you can assume 1 <= M, N <= 50.

Output

For each test case, output in one line the least number of wellsprings needed.

Sample Input
2 2 DK HF 3 3 ADC FJK IHE -1 -1 Sample Output 2 3

题意 一只狗要逃离迷宫 可以往上下左右4个方向走 每走一步耗时1s 每个格子只能走一次且迷宫的门只在t时刻打开一次 问狗是否有可能逃离这个迷宫

直接DFS 直道找到满足条件的路径 或者走完所有可能路径都不满足

注意剪枝 当前位置为(r,c) 终点为(ex,ey) 剩下的时间为lt 当前点到终点的直接距离为 d=(ex-r)+(ey-c) 若多走的时间rt=lt-d<0 或为奇数时 肯定是不可能的 可以自己在纸上画一下 每个点只能走一次的图 走弯路的话多走的步数一定为偶数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include<cstdio>
#include<cmath>
using namespace std;
int dx[4] = {0, 0, -1, 1};
int dy[4] = { -1, 1, 0, 0};
const int N = 10;
char mat[N][N];
bool ans;
int t, sx, sy, ex, ey;

void dfs(int r, int c, int lt)
{
    if(mat[r][c] == 'D' && lt == 0||ans)  //满足条件或已经满足条件
    {
        ans = true;
        return;
    }
    char tc=mat[r][c];  //保存原来的可能值 有'D'和'.'两种情况
    mat[r][c] = 'X';
    int rt = lt - abs(ex - r) - abs(ey - c);  //比直线到达终点多用的时间
    if(rt >= 0 && rt % 2 == 0)   //剪枝
    for(int i = 0; i < 4; ++i)   //4个方向走
    {
        int x = r + dx[i], y = c + dy[i];
        if(mat[x][y] == '.' || mat[x][y] == 'D')
            dfs(x, y, lt - 1);
    }
    mat[r][c] = tc;  //恢复原状
}

int main()
{
    int n, m;
    while(scanf("%d%d%d", &n, &m, &t), n)
    {
        for(int i = 1; i <= n; ++i)
            scanf("%s", mat[i] + 1);
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
            {
                if(mat[i][j] == 'S') sx = i, sy = j;
                if(mat[i][j] == 'D') ex = i, ey = j;
            }

        ans = false;
        dfs(sx, sy, t);
        printf(ans ? "YES\n" : "NO\n");
    }
    return 0;
}

Tempter of the Bone Time Limit:2 Seconds Memory Limit:65536 KB

The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.

Input
The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
‘X’: a block of wall, which the doggie cannot enter;
‘S’: the start point of the doggie;
‘D’: the Door; or
‘.’: an empty block.
The input is terminated with three 0’s. This test case is not to be processed.

Output
For each test case, print in one line “YES” if the doggie can survive, or “NO” otherwise.

Sample Input
4 4 5
S.X.
..X.
..XD
….
3 4 5
S.X.
..X.
…D
0 0 0

Sample Output
NO
YES

题意 中文

根据Havel-Hakimi定理构图就行咯 先把顶点按度数从大到小排序 可图的话 度数大的顶点与它后面的度数个顶点相连肯定是满足的 出现了-1就说明不可图了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20;
int mat[N][N], ord[N];

bool cmp(int i, int j)
{
    return mat[i][0] > mat[j][0];
}

int main()
{
    int cas, i, j, k, t, n;
    scanf("%d", &cas);
    while(cas--)
    {

        memset(mat, 0, sizeof(mat));
        scanf("%d", &n);
        for(i = 1; i <= n; ++i)
        {
            scanf("%d", &mat[i][0]);
            ord[i] = i;
        }

        for(i = 1; i <= n; ++i)
        {
            sort(ord + i, ord + n + 1, cmp);
            t = ord[i];
            if(mat[t][0] < 0) break;
            for(j = 1; j <= mat[t][0]; ++j)
            {
                k = ord[i + j];
                mat[t][k] = mat[k][t] = 1;
                --mat[k][0];
            }
        }

        if(i <= n) printf("NO\n");
        else
        {
            printf("YES\n");
            for(i = 1; i <= n; ++i)
            {
                for(int j = 1; j <= n; ++j)
                    printf("%d ", mat[i][j]);
                printf("\n");
            }
        }
        if(cas) printf("\n");
    }
    return 0;
}

Frogs’ Neighborhood

Description
未名湖附近共有N个大小湖泊L1, L2, …, Ln(其中包括未名湖)，每个湖泊Li里住着一只青蛙Fi(1 ≤ i ≤ N)。如果湖泊Li和Lj之间有水路相连，则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, …, xn，请你给出每两个湖泊之间的相连关系。

Input

第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行，第一行是整数N(2 < N < 10)，第二行是N个整数，x1, x2,…, xn(0 ≤ xi ≤ N)。

Output

对输入的每组测试数据，如果不存在可能的相连关系，输出”NO”。否则输出”YES”，并用N×N的矩阵表示湖泊间的相邻关系，即如果湖泊i与湖泊j之间有水路相连，则第i行的第j个数字为1，否则为0。每两个数字之间输出一个空格。如果存在多种可能，只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。

Sample Input

3 7 4 3 1 5 4 2 1 6 4 3 1 4 2 0 6 2 3 1 1 2 1

Sample Output

YES 0 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 NO YES 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0

Source

POJ Monthly–2004.05.15 Alcyone@pku

题意 求n/*m矩阵中‘@’连通块的个数 两个‘@’在一个九宫格内就属于一个连通块

最基础的DFS 遇到@就递归扫描周围8个并标记当前格子已访问 然后就得到答案了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include<cstdio>
using namespace std;
const int N = 110;
char mat[N][N];

int dfs(int r, int c)
{
    if(mat[r][c] != '@') return 0;
    else
    {
        mat[r][c] = '*';
        for(int i = -1; i <= 1; ++i)
            for(int j = -1; j <= 1; ++j)
                if(mat[r + i][c + j] == '@')
                    dfs(r + i, c + j);
    }
    return 1;
}

int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) , m)
    {
        for(int i = 1; i <= n; ++i)
            scanf("%s", mat[i] + 1);

        int ans = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                ans += dfs(i, j);
        printf("%d\n", ans);
    }
    return 0;
}

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.

The input file 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 and . 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.

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

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

0 1 2 2

题意 可以用一个四分图表示一32/*32的黑白图像 求两个四分树对应图像相加所得图形黑色部分有多少像素

直接用一个32/*32的矩阵表示图 黑色为非0白色为0 递归建图 最后有多少个非零就是答案了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include<cstdio>
#include<cstring>
using namespace std;
const int L = 32, N = 1050;
char s[N];
int ans[L][L], cnt;

void draw(char *s, int &p, int r, int c, int w)
{
    char ch = s[p++];
    if(ch == 'p')
    {
        draw(s, p, r        , c + w / 2, w / 2);
        draw(s, p, r        , c        , w / 2);
        draw(s, p, r + w / 2, c        , w / 2);
        draw(s, p, r + w / 2, c + w / 2, w / 2);
    }
    else if(ch == 'f')
    {
        for(int i = r; i < r + w; ++i)
            for(int j = c; j < c + w; ++j)
                if(ans[i][j] == 0)
                    ans[i][j] = ++cnt;
    }
}

int main()
{
    int cas;
    scanf("%d", &cas);
    while(cas--)
    {
        memset(ans, 0, sizeof(ans));
        cnt = 0;
        for(int i = 0; i < 2; ++i)
        {
            scanf("%s", s);
            int p = 0;
            draw(s, p, 0, 0, L);
        }
        printf("There are %d black pixels.\n", cnt);
    }
    return 0;
}

A quadtree is a representation format used to encode images. The fundamental idea behind the quadtree is that any image can be split into four quadrants. Each quadrant may again be split in four sub quadrants, etc. In the quadtree, the image is represented by a parent node, while the four quadrants are represented by four child nodes, in a predetermined order.

Of course, if the whole image is a single color, it can be represented by a quadtree consisting of a single node. In general, a quadrant needs only to be subdivided if it consists of pixels of different colors. As a result, the quadtree need not be of uniform depth.

A modern computer artist works with black-and-white images of units, for a total of 1024 pixels per image. One of the operations he performs is adding two images together, to form a new image. In the resulting image a pixel is black if it was black in at least one of the component images, otherwise it is white.

This particular artist believes in what he calls the preferred fullness: for an image to be interesting (i.e. to sell for big bucks) the most important property is the number of filled (black) pixels in the image. So, before adding two images together, he would like to know how many pixels will be black in the resulting image. Your job is to write a program that, given the quadtree representation of two images, calculates the number of pixels that are black in the image, which is the result of adding the two images together.

In the figure, the first example is shown (from top to bottom) as image, quadtree, pre-order string (defined below) and number of pixels. The quadrant numbering is shown at the top of the figure.

Input Specification

The first line of input specifies the number of test cases (N) your program has to process.

The input for each test case is two strings, each string on its own line. The string is the pre-order representation of a quadtree, in which the letter ‘p’ indicates a parent node, the letter ‘f’ (full) a black quadrant and the letter ‘e’ (empty) a white quadrant. It is guaranteed that each string represents a valid quadtree, while the depth of the tree is not more than 5 (because each pixel has only one color).

Output Specification

For each test case, print on one line the text ‘There are X black pixels.’, where X is the number of black pixels in the resulting image.

Example Input

3 ppeeefpffeefe pefepeefe peeef peefe peeef peepefefe

Example Output

There are 640 black pixels. There are 512 black pixels. There are 384 black pixels.