3020116_ac_3183ms_1004k.cc

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

#include <stdio.h>
#include <string.h>

int n;
int mtr[201][201];

int abs(int num)
{
	if(num < 0)
		return -num;
	else
		return num;
}

int valid(int a,int b)
{
	if(a<0||b<0||a>=n||b>=n)
		return 0;
	else
		return 1;
}

typedef struct node
{
	int a, b, c;
}type;

int find_nearest(int a,int b)
{
	int mark[201][201], ret, deep;
	int dis[401];
	int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0}};
	type que[40001], t, tt;
	int i, f, r;
	int aa, bb;

	ret = 0;
	memset(dis,0,sizeof(dis));
	memset(mark,0,sizeof(mark));
	mark[a][b] = 1;
	f = r = -1;
	t.a = a;t.b = b;t.c = 0;
	que[++r] = t;
	dis[0] = 1;
	deep = 1000;
	while(f!=r)
	{
		t = que[++f];
		if(t.c >= deep)
			break;
		a = t.a;
		b = t.b;
		for(i = 0; i < 4; i++)
		{
			aa = a+mov[i][0];bb = b+mov[i][1];
			if(valid(aa,bb)&&!mark[aa][bb])
			{
				mark[aa][bb] = 1;
				if(mtr[aa][bb]!=0)
				{
					if(dis[t.c+1]==0)
					{
						dis[t.c+1] = 1;
						deep = t.c+1;
						ret = mtr[aa][bb];
					}
					else
					{
						return 0;
					}
				}
				tt.a = aa;tt.b = bb;tt.c = t.c+1;
				que[++r] = tt;
			}
		}
	}
	return ret;
}

int main()
{
	int i, j;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			scanf("%d",&mtr[i][j]);
		}
	}
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			if(mtr[i][j]!=0)
			{
				printf("%d",mtr[i][j]);
			}
			else
			{
				printf("%d",find_nearest(i,j));
			}
			if(j==n-1)
				printf("\n");
			else
				printf(" ");
		}
	}
	return 0;
}