erp.cpp

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

#include <fstream>
#include <iostream>
#include <string.h>

using namespace std;

ifstream fin("erp.in");
ofstream fout("erp.out");

const int MAX = 30+5, dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

int n, m;
char map[MAX][MAX];
int st[MAX][MAX][4];



main() {
	fin >> n >> m;
	
	memset(st, 0x3F, sizeof(st));
	int i, j, k, d;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			fin >> map[i][j];
			switch (map[i][j]) {
				case 'S': st[i][j][0] = 0; break;
				case 'E': st[i][j][1] = 0; break;
				case 'N': st[i][j][2] = 0; break;
				case 'W': st[i][j][3] = 0; break;
			}
		}
		
	int more = 1;
	while (more) {
		more = 0;
		
		for (i = 0; i < n; i++)
			for (j = 0; j < m; j++)
				for (d = 0; d < 4; d++) {
					int cost[4] = {5, 0, 1, 10}, ok = 0, d0 = (d + 3) % 4;
					for (k = 0; k < 4; k++, d0 = (d0 + 1) % 4) {
						if (k == 3 && ok) break;
						int x = i + dir[d0][0], y = j + dir[d0][1];
						if (x < 0 || x == n || y < 0 || y == m || map[x][y] == '.') continue;
						ok = 1;
						if (st[i][j][d] + cost[k] < st[x][y][d0])
							st[x][y][d0] = st[i][j][d] + cost[k], more = 1;
					}
				}
	}
	
	int best = 2147483647;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) if (map[i][j] == 'F')
			for (k = 0; k < 4; k++)
				if (st[i][j][k] < best)
					best = st[i][j][k];
			
	fout << best << endl;	
	
	return 0;	
}