2015318_ac_15ms_256k.c

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

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

int r, c, R, C;
int sti, stj;
char grove[50][51];

int bfs(int d)
{
	int i;
	int f, p;
	int ti, tj;
	int ans[50][51];
	int queue[25000][2];

	memset(ans,0,sizeof(ans));
	for(i = r; i < C; i++)
		ans[c][i] = -1;
	f = 0; p = 0;

	if(grove[c+d][r]!='X')
	{
	    p++;
    	queue[p][0] = c+d;
    	queue[p][1] = r;
    	ans[c+d][r] = 1;
	   	if(grove[c+d][r]=='*')
	    	return 1;
	}
    if(r<C-1&&grove[c+d][r+1]!='X')
	{
	   	p++;
    	queue[p][0] = c+d;
    	queue[p][1] = r+1;
    	ans[c+d][r+1] = 1;
	   	if(grove[c+d][r+1]=='*')
	    	return 1;
	}
	if(r>0&&grove[c+d][r-1]!='X')
	{
	   	p++;
	   	queue[p][0] = c+d;
	   	queue[p][1] = r-1;
	   	ans[c+d][r-1] = 1;
	   	if(grove[c+d][r-1]=='*')
 	   		return 1;
	}
	while(f!=p)
	{
		f++;
		ti = queue[f][0];
		tj = queue[f][1];
		
		if(ti<R-1)
		{
			if(tj<C-1&&ans[ti+1][tj+1]==0&&grove[ti+1][tj+1]!='X')
			{
				p++;
				queue[p][0] = ti+1;
				queue[p][1] = tj+1;
				ans[ti+1][tj+1] = ans[ti][tj]+1;
				if(grove[ti+1][tj+1]=='*')
					return ans[ti+1][tj+1];
			}
			if(tj>0&&ans[ti+1][tj-1]==0&&grove[ti+1][tj-1]!='X')
			{
				p++;
				queue[p][0] = ti+1;
				queue[p][1] = tj-1;
				ans[ti+1][tj-1] = ans[ti][tj]+1;
				if(grove[ti+1][tj-1]=='*')
					return ans[ti+1][tj-1];
			}
			if(ans[ti+1][tj]==0&&grove[ti+1][tj]!='X')
			{
				p++;
				queue[p][0] = ti+1;
				queue[p][1] = tj;
				ans[ti+1][tj] = ans[ti][tj]+1;
				if(grove[ti+1][tj]=='*')
					return ans[ti+1][tj];
			}
			
		}
		if(ti>0)
		{
			if(tj<C-1&&ans[ti-1][tj+1]==0&&grove[ti-1][tj+1]!='X')
			{
				p++;
				queue[p][0] = ti-1;
				queue[p][1] = tj+1;
				ans[ti-1][tj+1] = ans[ti][tj]+1;
				if(grove[ti-1][tj+1]=='*')
					return ans[ti-1][tj+1];
			}
			if(tj>0&&ans[ti-1][tj-1]==0&&grove[ti-1][tj-1]!='X')
			{
				p++;
				queue[p][0] = ti-1;
				queue[p][1] = tj-1;
				ans[ti-1][tj-1] = ans[ti][tj]+1;
				if(grove[ti-1][tj-1]=='*')
					return ans[ti-1][tj-1];
			}
			if(ans[ti-1][tj]==0&&grove[ti-1][tj]!='X')
			{
				p++;
				queue[p][0] = ti-1;
				queue[p][1] = tj;
				ans[ti-1][tj] = ans[ti][tj]+1;
				if(grove[ti-1][tj]=='*')
					return ans[ti-1][tj];
			}
			
		}
		if(tj>0&&ans[ti][tj-1]==0&&grove[ti][tj-1]!='X')
		{
			p++;
			queue[p][0] = ti;
			queue[p][1] = tj-1;
			ans[ti][tj-1] = ans[ti][tj]+1;
			if(grove[ti][tj-1]=='*')
				return ans[ti][tj-1];
			
		}
		if(tj<C-1&&ans[ti][tj+1]==0&&grove[ti][tj+1]!='X')
		{
			p++;
			queue[p][0] = ti;
			queue[p][1] = tj+1;
			ans[ti][tj+1] = ans[ti][tj]+1;
			if(grove[ti][tj+1]=='*')
				return ans[ti][tj+1];
			
		}
	}
	return 1;
}

void input()
{
	int i, j;

	scanf("%d%d",&R,&C);
	r = -1;
	for(i = 0; i < R; i++)
	{
		getchar();
		for(j = 0; j < C; j++)
		{
			scanf("%c",&grove[i][j]);
			if(grove[i][j]=='*')
			{
				sti = i;
				stj = j;
			}
			if(grove[i][j]=='X'&&j>r)
			{
				r = j;
				c = i;
			}
		}
	}
}

void output()
{
	r++;
	printf("%d",bfs(-1)+bfs(1));
}

int main()
{
	input();
	output();
	return 1;
}