1957079_ac_217ms_11056k.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MAX 751

struct node
{
	int h;
	int w;
}pos[MAX];

int W, H, M;
int B[MAX][MAX];
int K[MAX][MAX];
int Ni[MAX][MAX];
static int num4 = 0;

void bfs_4(int w, int h, int a[][MAX])
{
	int queue[562501][2];
	long f, r;
	int tw, th;

	f = 0;r = 1;
	a[h][w] = 1;
	queue[r][0] = h;
	queue[r][1] = w;
	while(f!=r&&num4)
	{
		f++;
		tw = queue[f][1];
		th = queue[f][0];
		if(th<H-1&&a[th+1][tw]==0)
		{
			if(Ni[th+1][tw]==0||Ni[th+1][tw]==4)
			{
				r++;
				queue[r][0] = th+1;
				queue[r][1] = tw;
				a[th+1][tw] = a[th][tw]+1;
			}
		}
		if(th>0&&a[th-1][tw]==0)
		{
			if(Ni[th-1][tw]==0||Ni[th-1][tw]==4)
			{
				r++;
				queue[r][0] = th-1;
				queue[r][1] = tw;
				a[th-1][tw] = a[th][tw]+1;
			}
		}
		if(tw<W-1&&a[th][tw+1]==0)
		{
			if(Ni[th][tw+1]==0||Ni[th][tw+1]==4)
			{
				r++;
				queue[r][0] = th;
				queue[r][1] = tw+1;
				a[th][tw+1] = a[th][tw]+1;
			}
		}
		if(tw>0&&a[th][tw-1]==0)
		{
			if(Ni[th][tw-1]==0||Ni[th][tw-1]==4)
			{
				r++;
				queue[r][0] = th;
				queue[r][1] = tw-1;
				a[th][tw-1] = a[th][tw]+1;
			}

		}
	}
}
void input()
{
	int i, j, ans;
	int w2, h2;
	int w3, h3;

	scanf("%d%d",&W,&H);
	for(i = 0; i < H; i++)
		for(j = 0; j < W; j++)
		{
			scanf("%d",&Ni[i][j]);
			if(Ni[i][j] == 2)
			{
				w2 = j;
				h2 = i;
			}
			if(Ni[i][j] == 3)
			{
				w3 = j;
				h3 = i;
			}
			if(Ni[i][j] == 4)
			{
				pos[num4].w = j;
				pos[num4].h = i;
				num4++;
			}
		}
	M = num4;
	memset(B,0,sizeof(B));
	memset(K,0,sizeof(K));
	bfs_4(w2,h2,B);
	bfs_4(w3,h3,K);
	ans = 30000;
	for(i = 0; i < M; i++)
		if(K[pos[i].h][pos[i].w]&&B[pos[i].h][pos[i].w]&&B[pos[i].h][pos[i].w]+K[pos[i].h][pos[i].w]-2 < ans)
			ans = B[pos[i].h][pos[i].w]+K[pos[i].h][pos[i].w]-2;
	printf("%d\n",ans);
}
int main()
{
	input();
	return 1;
}