【nwpu暑假集训搜索专题】（二）

POJ 1111

联通块算周长

#include<iostream>
#include<cstring>
#include<cstdio>
#include<stdlib.h>
using namespace std;
int n, m, x1, y1, ans;
char a[200][200];
int map[200][200];

void change(int i, int j)
{
    int k,l;
    if (i < 1 || i > n || j < 1 || j > m) return;
    
    map[i][j] = 1;
    if(a[i - 1][j] == 'X' && (!map[i - 1][j]))  change(i - 1, j);
    if(a[i + 1][j] == 'X'&& (!map[i + 1][j]))  change(i + 1, j);
    if(a[i][j - 1] == 'X'&& (!map[i][j - 1]))  change(i, j - 1);
    if(a[i][j + 1] == 'X'&& (!map[i][j + 1]))  change(i, j + 1);
    if(a[i - 1][j - 1] == 'X'&& (!map[i - 1][j - 1]))  change(i - 1, j - 1);
    if(a[i + 1][j + 1] == 'X'&& (!map[i + 1][j + 1]))  change(i + 1, j + 1);
    if(a[i - 1][j + 1] == 'X'&& (!map[i - 1][j + 1]))  change(i - 1, j + 1);
    if(a[i + 1][j - 1] == 'X'&& (!map[i + 1][j - 1]))  change(i + 1, j - 1);
}

void calc()
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (map[i][j])
			{
				if (!map[i - 1][j]) ans++;
				if (!map[i + 1][j]) ans++;
				if (!map[i][j - 1]) ans++;
				if (!map[i][j + 1]) ans++;
			}
		}
	}
}
int main()
{
	while(scanf("%d%d%d%d", &n, &m, &x1, &y1) != EOF, n!=0 || m!=0 || x1!=0 || y1!=0)
	{
		for(int i = 1; i <= n; i++)
			scanf("%s", a[i] + 1);
		memset(map, 0, sizeof(map));
		map[x1][y1] = 1;
		ans = 0;
		change(x1, y1);
		calc();
		printf("%d\n", ans);
    }
    return 0;
}

POJ 2488

骑士游历计方案，注意因为字典序输出，所以需要注意mov数组的方向

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define maxn 26
struct Point
{
    int x, y;
}way[maxn * maxn];

bool map[maxn][maxn];
int p, q;
bool fou;
int mov[8][2] ={{-2, -1},{-2, 1},{-1, -2},{-1, 2},{1, -2},{1, 2},{2, -1},{2, 1}};

bool can(int x, int y)
{
    if (x < 0 || y < 0 || x >= q || y >= p)return false;
    if (map[x][y]) return false;
    return true;
}

void dfs(int x, int y, int dep)
{
    way[dep].x = x;
    way[dep].y = y;
    if (dep == p * q - 1)
    {
        fou = true;
        return;
    }
    for (int i = 0; i < 8; i++)
    {
        if (can(x + mov[i][0], y + mov[i][1]))
        {
            map[x + mov[i][0]][y + mov[i][1]] = true;
            dfs(x + mov[i][0], y + mov[i][1], dep + 1);
            if (fou) return;
            map[x + mov[i][0]][y + mov[i][1]] = false;
        }
    }
}

void print()
{
    for (int i = 0; i < p * q; i++)
        printf("%c%d", way[i].x + 'A', way[i].y + 1);
    printf("\n\n");
}

int main()
{
    int t;
    scanf("%d", &t);
    int s = 0;
    while (t--)
    {
        s++;
        printf("Scenario #%d:\n", s);
        memset(map, 0, sizeof(map));
        scanf("%d%d", &p, &q);
        for (int i = 0; i < q; i++)
        {
            for (int j = 0; j < p; j++)
            {
                fou = false;
                map[i][j] = true;
                dfs(i, j, 0);
                if (fou) break;
                map[i][j] = false;
            }
            if (fou) break;
        }
        if (fou)print();
        else printf("impossible\n\n");
    }
    return 0;
}

数联通块数目

#include<iostream>
#include<cstring>
#include<cstdio>
#include<stdlib.h>
using namespace std;
int n, m;
char a[200][200];
void init()
{
    memset(a, 0, sizeof(a));

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
    {
        cin >> a[i][j];
        if (a[i][j] == '@')
           a[i][j] = 1;
        else a[i][j] = 0;
    }
}
void change(int i, int j)
{
    int k,l;
    a[i][j] = 0;
    if(a[i - 1][j] > 0)  change(i - 1, j);
    if(a[i + 1][j] > 0)  change(i + 1, j);
    if(a[i][j - 1] > 0)  change(i, j - 1);
    if(a[i][j + 1] > 0)  change(i, j + 1);
    if(a[i - 1][j - 1] > 0)  change(i - 1, j - 1);
    if(a[i + 1][j + 1] > 0)  change(i + 1, j + 1);
    if(a[i - 1][j + 1] > 0)  change(i - 1, j + 1);
    if(a[i + 1][j - 1] > 0)  change(i + 1, j - 1);
}


int main()
{
    cin >> n >> m;
    while ((n != 0) && (m != 0))
    {
        init();

        int cnt = 0;
        for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if (a[i][j] != 0)
            {
                change(i, j);
                cnt++;
            }
        }
        cout << cnt << endl;
        cin >> n >> m;
    }
    return 0;
}

POJ 1564

给若干个数，求其中选一些数的和为指定数的所有方案……相同的不要，通过一个剪枝可以剪掉！

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, len, a[20], b[20], cnt;
inline bool cmp(int a, int b){ return a > b;} 
void print(int x)
{
	cnt++;  
    for(int i = 0; i < x; i++)  
    {  
		if(i) printf("+%d", b[i]);  
        else  printf("%d", b[i]);  
    }  
    printf("\n");  
}
void dfs(int x, int aa, int sum, int bb)  
{  
    if(sum > n)   return;  
    if(sum == n)  print(bb);

    for(int i = aa; i < len; i++)  
    {  
        b[bb] = a[i];  
        dfs(a[i], i + 1, sum + a[i], bb + 1);  
        while(i + 1 < len && a[i] == a[i + 1]) i++;  
    }  
}

int main()
{
    while(scanf("%d%d",&n, &len) != EOF && n + len != 0)
    {
        for(int i = 0; i < len; i++)
            scanf("%d", &a[i]);
        sort(a, a + len, cmp);
        printf("Sums of %d:\n", n);
        cnt = 0;
        dfs(0, 0, 0, 0);
        if(!cnt) printf("NONE\n");
    }

    return 0;
}