3020112_tle.cpp

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

#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

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

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

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

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}};

	ret = 0;
	memset(dis,0,sizeof(dis));
	memset(mark,0,sizeof(mark));
	mark[a][b] = 1;
	typedef pair <int,int> tmp;
	typedef pair <tmp,int> type;
	type t;
	queue <type> que;
	t.first.first = a;
	t.first.second = b;
	t.second = 0;
	que.push(t);
	dis[0] = 1;
	deep = 1000;
	while(!que.empty())
	{
		t = que.front();
		if(t.second >= deep)
			break;
		a = t.first.first;
		b = t.first.second;
		que.pop();
		for(int i = 0; i < 4; i++)
		{
			if(valid(a+mov[i][0],b+mov[i][1])&&!mark[a+mov[i][0]][b+mov[i][1]])
			{
				mark[a+mov[i][0]][b+mov[i][1]] = 1;
				if(mtr[a+mov[i][0]][b+mov[i][1]]!=0)
				{
					if(dis[t.second+1]==0)
					{
						dis[t.second+1] = 1;
						deep = t.second+1;
						ret = mtr[a+mov[i][0]][b+mov[i][1]];
					}
					else
					{
						return 0;
					}
				}
				que.push(make_pair(make_pair(a+mov[i][0],b+mov[i][1]),t.second+1));
			}
		}
	}
	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;
}