2329.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#define debug 0
#define NMAX 201
#define INF 30000
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int max(int a,int b)
{
	return a>b?a:b;
}

int min(int a,int b)
{
	return a<b?a:b;
}
int a[NMAX][NMAX];
int b[NMAX][NMAX];
int N;
int t[2]={1,-1};
int abs(int a)
{
	if(a<0)
		a=-a;
	return a;
}
void solve()
{
	int k,i,j;
	int p,q;
	int total,tmp,flag;
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=N;j++)
		{
			b[i][j]=a[i][j];
			if(!a[i][j])
			{
				for(k=1;k<=N*N;k++)
				{
					total=0;
					tmp=0;
					flag=0;
					for(p=-k;p<=k;p++)
					{
						int m;
						if(k-abs(p))
						{
							for(m=0;m<2;m++)
							{
								q=t[m]*(k-abs(p));
								if(i+q<1||j+p<1||i+q>N||j+p>N)
									continue;
								if(a[i+q][j+p])
								{
									if(tmp)
									{
										flag=1;
										tmp=0;
										break;
									}
									else
									{
										flag=1;
										tmp=a[i+q][j+p];
									}
								}
							}
						}
						else
						{
							q=t[0]*(k-abs(p));
							if(i+q<1||j+p<1||i+q>N||j+p>N)
								continue;
							if(a[i+q][j+p])
							{
								if(tmp)
								{
									flag=1;
									tmp=0;
									break;
								}
								else
								{
									flag=1;
									tmp=a[i+q][j+p];
								}
							}
						}
						if(!tmp&&flag)
							break;

					}
					if(flag)
					{
						b[i][j]=tmp;
						break;
					}
				}
			}
		}
	}

}
int main()
{

#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int i,j;
	scanf("%d",&N);
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			scanf("%d",&a[i][j]);
	solve();
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=N;j++)
			printf("%d ",b[i][j]);
		printf("\n");
	}
#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}