pku 1164

这道题其实就是求连通块的个数,及最大的连通块,题目输入表示一个块四周的墙要处理下,将块的表示数字分别与1, 2, 4, 8相与得到在W,N,E,S是否有墙。

代码如下:

 

#include <stdio.h>
#include <string.h>
#define MAXN 102
char map[MAXN][MAXN];
int mask[4] = {1, 2, 4, 8};
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int cnt, max, tot, n, m;
void init()
{
	int x, y, i, j, k, p;
	scanf("%d %d", &n, &m);
	memset(map, '#', sizeof(map));
	for(i = 1;i <= n; i++)
	{
		for(j = 1;j <= m; j++)
		{
			scanf("%d", &p);
			x = i << 1;
			y = j << 1;
			map[x][y] = ' ';
			for(k = 0;k < 4; k++)
				if((p & mask[k]) == 0) map[x + dx[k]][y + dy[k]] = ' ';
		}
	}
	n <<= 1; n++;
	m <<= 1; m++;
}
void dfs(int x, int y)
{
	int tx, ty, i;
	map[x][y] = '*';
	if(x % 2 == 0 && y % 2 == 0) cnt++;
	for(i = 0;i < 4; i++)
	{
		tx = x + dx[i];
		ty = y + dy[i];
		if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
		if(map[tx][ty] != ' ') continue;
		dfs(tx, ty);
	}
}
void solve()
{
	int i, j;
	tot = 0;
	max = 0;
	for(i = 1;i <= n; i++)
	{
		for(j = 1;j <= m; j++)
		{
			if(map[i][j] == ' ')
			{
				tot++;
				cnt = 0;
				dfs(i, j);
				if(max < cnt) max = cnt;
			}
		}
	}
	printf("%d\n", tot);
	printf("%d\n", max);
}
int main()
{
	init();
	solve();
	return 0;
}

 

 

pku 1166

这题我用位运算+bfs过了,时间有些长,这题还可以用数学方法:高斯消元。

代码:

 

#include <stdio.h>
#include <string.h>
#define BITAT(x,i) (((x)>>(9-(i)))&1)
#define MAXN 1<<20
int mask[10] = {0, 432, 448, 216, 292, 186, 73, 54, 7, 27};
int pre[MAXN][2];
int que[MAXN];
int head, tail, st;
void init()
{
	int i, x;
	st = 0;
	for(i = 1;i <= 9; i++)
	{
		scanf("%d", &x);
		st = (st<<2) | x;
	}
}
void bfs()
{
	int cur, tmp, i, j, k, t;
	memset(pre, -1, sizeof(pre));
	que[0] = st;
	head = 0;
	tail = 1;
	while(head < tail)
	{
		cur = que[head];
		for(j = 1;j <= 9; j++)
		{
			tmp = 0;
			for(i = 1;i <= 9; i++)
			{
				k = (cur>>(18 - i * 2)) & 3;
				t = BITAT(mask[j], i);
				k = (k + t) - (((k + t)>>2)<<2);
				tmp = (tmp<<2) | k;
			}
			if(pre[tmp][0] == -1)
			{
				pre[tmp][0] = cur;
				pre[tmp][1] = j;
				if(tmp == 0) return;
				que[tail++] = tmp;
			}
		}
		head++;
	}
}
void output()
{
	int i, j;
	i = 0; j = 0;
	while(i != st)
	{
		que[++j] = pre[i][1];
		i = pre[i][0];
	}
	for(i = j;i > 1; i--) printf("%d ", que[i]);
	printf("%d\n", que[1]);
}
int main()
{
	init();
	bfs();
	output();
	return 0;
}

 

 

代码2:

 

#include <stdio.h>
#include <string.h>
#define MAXN 1<<20
int act[9][9] = {{1, 1, 0, 1, 1, 0, 0, 0, 0},
	         {1, 1, 1, 0, 0, 0, 0, 0, 0},
	         {0, 1, 1, 0, 1, 1, 0, 0, 0},
		 {1, 0, 0, 1, 0, 0, 1, 0, 0},
		 {0, 1, 0, 1, 1, 1, 0, 1, 0},
		 {0, 0, 1, 0, 0, 1, 0, 0, 1},
		 {0, 0, 0, 1, 1, 0, 1, 1, 0},
		 {0, 0, 0, 0, 0, 0, 1, 1, 1},
		 {0, 0, 0, 0, 1, 1, 0, 1, 1}};
int pre[MAXN][2];
int que[MAXN];
int head, tail, st;
void init()
{
	int i, x;
	st = 0;
	for(i = 1;i <= 9; i++)
	{
		scanf("%d", &x);
		st = (st<<2) | x;
	}
}
void bfs()
{
	int cur, tmp, i, j, k, t;
	memset(pre, -1, sizeof(pre));
	que[0] = st;
	head = 0;
	tail = 1;
	while(head < tail)
	{
		cur = que[head];
		for(i = 1;i <= 9; i++)
		{
			tmp = 0;
			for(j = 1;j <= 9; j++)
			{
				k = (cur>>(18 - j * 2)) & 3;
				t = act[i-1][j-1];
				k = (k + t) - (((k+t)>>2)<<2);
				tmp = (tmp<<2) | k;
			}
			if(pre[tmp][0] == -1)
			{
				pre[tmp][0] = cur;
				pre[tmp][1] = i;
				if(tmp == 0) return;
				que[tail++] = tmp;
			}
		}
		head++;
	}
}
void output()
{
	int i, j;
	i = 0; j = 0;
	while(i != st)
	{
		que[++j] = pre[i][1];
		i = pre[i][0];
	}
	for(i = j;i > 1; i--) printf("%d ", que[i]);
	printf("%d\n", que[1]);
}
int main()
{
	init();
	bfs();
	output();
	return 0;
}

 

 

pku 3185

这道题与以前的一道翻转棋的类似,我用二进制表示状态,用异或运算实现一个状态到令一个状态的转移。

代码:

 

#include <stdio.h>
#include <string.h>
#define MAXM 1<<21
#define MAXN 20
int act[MAXN] = { 3, 7, 14, 28, 56, 112, 224, 448, 896, 1792, 3584, 7168, 14336, 28672, 57344, 114688, 229376, 458752, 917504, 786432 };
int que[MAXM];
int dis[MAXM];
int head, tail;
int st;
void init()
{
	int i, x;
	for(st = 0, i = 1;i <= 20; i++)
	{
		scanf("%d", &x);
		st = st * 2 + x;
	}
}
void bfs()
{
	int i, j, t;
	memset(dis, -1, sizeof(dis));
	dis[st] = 0;
	que[0] = st;
	head = 0;
	tail = 1;
	while(head < tail)
	{
		i = que[head];
		for(j = 0;j < 20; j++)
		{
			t = i ^ act[j];
			if(dis[t] == -1)
			{
				dis[t] = dis[i] + 1;
				if(t == 0) return;
				que[tail++] = t;
			}
		}
		head++;
	}
}
int main()
{
	init();
	bfs();
	printf("%d\n", dis[0]);
	return 0;
}

 

 

本地评测工具

呵呵,睡不着,爬起来写个测试工具,挺好玩的,呵呵,这样方便以后测试程序了,不要一个个的敲命令了。
发下截图:

ps: 时间是2009-08-17 03:05

 

pku1556

计算几何+最短路

思路:把起点,终点,以及门的两个点作为无向图的点建图。两个点可达当且仅当它们可以直线可达,这里用判线相交判断。
代码:

 

#include <stdio.h>
#include <math.h>
#include <string.h>
#define SQR(x) ((x)*(x))
#define oo 9999999999.999
#define eps 1e-16
#define MAXE 120002
#define MAXV 102
#define MAXN 18
typedef struct {  int u; int v; double w; int next;}edge_t;
typedef struct { double x; double y;}pt_t;
edge_t e[MAXE];
pt_t door[MAXN * 4 + 1];
pt_t wall[MAXN * 3 + 1][2];
double dis[MAXV];
int first[MAXV];
int que[MAXV * MAXV];
int has[MAXV];
int head, tail;
int ndoor, nwall;
int tot, st, ed, n;
int dcmp(double x)
{
	if(x < -eps) return -1;
	return x > eps;
}
double cross(double x1, double y1, double x2, double y2)
{
	return x1 * y2 - x2 * y1;
}
int segcross(pt_t a, pt_t b, pt_t c, pt_t d)
{
	int u = dcmp(cross(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y) * cross(b.x - a.x, b.y - a.y, d.x - a.x, d.y - a.y));
	int v = dcmp(cross(d.x - c.x, d.y - c.y, a.x - c.x, a.y - c.y) * cross(d.x - c.x, d.y - c.y, b.x - c.x, b.y - c.y));
	return u < 0 && v < 0;
}
void add(int u, int v, double w)
{
	e[++tot].u = u; e[tot].v = v; e[tot].w = w; e[tot].next = first[u]; first[u] = tot;
	e[++tot].u = v; e[tot].v = u; e[tot].w = w; e[tot].next = first[v]; first[v] = tot;
}
void add_door(double x, double y)
{
	++ndoor;
	door[ndoor].x = x;
	door[ndoor].y = y;
}
void add_wall(double x1, double y1, double x2, double y2)
{
	++nwall;
	wall[nwall][0].x = x1;
	wall[nwall][0].y = y1;
	wall[nwall][1].x = x2;
	wall[nwall][1].y = y2;
}
int init()
{
	double x, y1, y2, y3, y4;
	int i;
	scanf("%d", &n);
	if(n == -1) return 0;
	ndoor = 0; nwall = 0;
	add_door(0.0, 5.0);
	for(i = 1;i <= n; i++)
	{
		scanf("%lf %lf %lf %lf %lf", &x, &y1, &y2, &y3, &y4);
		add_door(x, y1);
		add_door(x, y2);
		add_door(x, y3);
		add_door(x, y4);
		add_wall(x, 0.0, x, y1);
		add_wall(x, y2,  x, y3);
		add_wall(x, y4,  x, 10);
	}
	add_door(10.0, 5.0);
	return 1;
}
double dist(pt_t p1, pt_t p2)
{
	return sqrt(SQR(p1.x - p2.x) + SQR(p1.y - p2.y));
}
int check(pt_t a, pt_t b)
{
	int i;
	for(i = 1;i <= nwall; i++) if(segcross(a, b, wall[i][0], wall[i][1])) return 0;
	return 1;
}
void build()
{
	double len;
	int i, j;
	memset(first, -1, sizeof(first));
	tot = -1;
	for(i = 1;i <= ndoor; i++)
	{
		for(j = i + 1;j <= ndoor; j++)
		{
			if(dcmp(fabs(door[i].x - door[j].x)) == 0) continue;
			if(check(door[i], door[j]) == 0) continue;
			len = dist(door[i], door[j]);
			add(i, j, len);
		}
	}
	st = 1; ed = ndoor;
}
void spfa()
{
	int i, j, t;
	for(i = st;i <= ed; i++) dis[i] = oo;
	memset(has, 0, sizeof(has));
	dis[st] = 0.0; has[st] = 1;
	que[0] = st; head = 0; tail = 1;
	while(head < tail)
	{
		i = que[head]; has[i] = 0;
		t = first[i];
		while(t != -1)
		{
			j = e[t].v;
			if(dis[i] + e[t].w + eps < dis[j])
			{
				dis[j] = dis[i] + e[t].w;
				if(has[j] == 0)
				{
					que[tail++] = j;
					has[j] = 1;
				}
			}
			t = e[t].next;
		}
		head++;
	}
}
int main()
{
	while(init())
	{
		build();
		spfa();
		printf("%0.2lf\n", dis[ed]);
	}
	return 0;
}