pils.c

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

#include <stdio.h>
#define max 214743647

int n,m,i,j,k,l;
int num[101][101];
int opt[101][101][9];
int on[101][101];
int ref;
int dx[9]={0, 0,-1,0,1,-1,-1,1,1};
int dy[9]={0,	1,0,-1,0,1,-1,-1,1};
int nx,ny,min;

int main()
{
	FILE* inf=fopen("pils.in","r");
	FILE* outf=fopen("pils.out","w");

	fscanf(inf,"%d %d\n",&n,&m);
	for (i=1; i<=m; i++) {
		for (j=1; j<=n; j++)
			fscanf(inf," %d",&num[i][j]);
		fscanf(inf,"\n");
	}
	fclose(inf);

	for (i=1; i<=m; i++)
		for (j=1; j<=n; j++)
			for (k=1; k<=8; k++)
				opt[i][j][k]=max;
	for (i=1; i<=8; i++)
		opt[1][1][i]=0;
	on[1][1]=1;
	do {
		ref=0;
		for (i=1; i<=m; i++) {
			for (j=1; j<=n; j++) {
				if (on[i][j]) {
					on[i][j]=0;
					for (k=1; k<=8; k++) {
						nx=i+dx[k]*num[i][j]; ny=j+dy[k]*num[i][j];
						if (nx>=1 && nx<=m && ny>=1 && ny<=n) {
							for (l=1; l<=8; l++) {
								if (l!=k && opt[i][j][l]<max && opt[i][j][l]+1<opt[nx][ny][k]) {
									opt[nx][ny][k]=opt[i][j][l]+1;
									ref=1;
									on[nx][ny]=1;
								}
							}
						}
					}
				}
			}
		}
	} while (ref==1);

	min=opt[m][n][1];
	for (i=2; i<=8; i++)
		if (opt[m][n][i]<min)
			min=opt[m][n][i];

	if (min==max)
		fprintf(outf,"NEVAR");
	else
		fprintf(outf,"%d",min);
	fclose(outf);

	return 0;
}