#include <stdio.h>
#include <math.h>

#define MAX 200000
#define RAN 300

struct pos{
	int x,y;
};

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

struct pos tar;
int min, m, n;
int val[RAN][RAN];

int main()
{
	int i,j;
	struct pos start;
	void dfs(int, int, int);
	char ch;

	scanf("%d%d",&m,&n);
	while(m && n)
	{
		min = MAX;
		for(i = 0;i < RAN; i++)
			for(j = 0;j < RAN; j++) {
				val[i][j]=0;
		 	}
		
		for(i = 0; i < m; i++) {
			scanf("%c", &ch);
			for(j = 0; j < n; j++) {
				scanf("%c",&ch);
				if(ch=='Y') {
					start.x = i;
					start.y = j;
				}
				if(ch=='T') {
					tar.x = i;
					tar.y = j;
					val[i][j] = 1;
				}
				if(ch == 'E')
					val[i][j] = 1;
				if(ch == 'B')
					val[i][j] = 2;
				if(ch == 'R' || ch == 'S')
					val[i][j]=MAX;
			}
		}
		
		dfs(start.x, start.y, 0);    
		if (min != MAX)
			printf("%d\n", min);
		else
			printf("-1\n");
		scanf("%d%d", &m, &n);
	}
	return 0;    
}

void dfs(int x, int y, int cost)
{
	int i;
	if (x == tar.x && y == tar.y) {
		if (cost < min)
			min = cost;
	}
	else if (cost + abs(tar.x - x) + abs(tar.y - y) < min) 
	for (i = 0; i < 4; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];
		if (val[tx][ty] != MAX)
			if (val[tx][ty] >= 0)
		    		if (tx >= 0 && ty >= 0 && tx < m && ty < n) {
					val[x][y] = -val[x][y];
					dfs(tx, ty, cost + val[tx][ty]);
					val[x][y] = -val[x][y];
				}
	}
}

• Re:为什么总是超时 (17) Ethanh 2005-03-28 14:44:07
  • Re:为什么总是超时 (2337) Ethanh 2005-03-28 14:55:02