目录

挑战程序设计竞赛第一章&第二章例题总结(正在写)

本文主要内容
第一章&第二章的例题,自己做了一遍的心得&分析。

思维

POJ-1852 Ants

原题链接

思路
对于最短耗费时间,蚂蚁朝近的端点走即可,此时没有相遇的情况,离自己的近端点最远的蚂蚁行走所耗费时间即是答案。
对于最长耗费时间,显然,两蚂蚁相遇再掉头折返走到端点和两蚂蚁相遇之后继续朝原来的方向走到端点所花费的时间是相同的,所以可将每一只蚂蚁看作是独立的,朝远的端点走即可。离自己的远端点最远的蚂蚁行走所耗费时间即为答案。
参考代码
#include <iostream>
#include <algorithm>
using namespace std;

int main(void)
{
	int T;
	cin >> T;
	while(T--)
	{
		int len, n;
		cin >> len >> n;
		int maxTime = 0, minTime = 0;
		for(int i = 0; i < n; i++)
		{
			int posTmp;
			cin >> posTmp;
			minTime = max(minTime, min(posTmp, len-posTmp));
			maxTime = max(maxTime, max(posTmp, len-posTmp));
		}
		cout << minTime << ' ' << maxTime << endl;
	}
	return 0;
}

深度优先搜索

POJ-2386 Lake Counting

原题链接

思路
dfs,需要注意的是,一篇池塘搜索完之后需要停止搜索,另外在标记搜索过的方块时,搜索起点不要忘记标记。
参考代码
#include <cstdio>
using namespace std;

const int maxn = 110;
char field[maxn][maxn];
int n, m, res;
int dx[8] = {-1, 0, 1, 0, -1, 1, -1, 1}, dy[8] = {0, -1, 0, 1, -1, 1, 1, -1};

void dfs(int x, int y)
{
    int flag = 1;	//标记当前这片池塘是否搜完
    for(int i = 0; i < 8; i++)
    {
        int tmpX = x + dx[i], tmpY = y + dy[i];
        if(tmpX >= 0 && tmpX < n && tmpY >= 0 && tmpY < m && field[tmpX][tmpY] == 'W')
        {
            //printf("%d %d\n", tmpX, tmpY);
            flag = 0;	//相邻的方块中还有水,则这片池塘还没被搜完
            field[tmpX][tmpY] = '.';	//搜过的地方标记为没水的土地,防止重复
            dfs(tmpX, tmpY);
            if(flag) return;	//搜完了就结束循环
        }
    }
}

int main(void)
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        getchar();
        for(int j = 0; j < m; j++)
            scanf("%c", &field[i][j]);
    }

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(field[i][j] == 'W')
            {
                res++;	//这个方块可以形成池塘,池塘数加1
                field[i][j] = '.';
                dfs(i, j);
            }
        }
    }
    printf("%d\n", res);

    return 0;
}