USACO Training Section 2.4 Overfencing

英文原题  中文题译 

大意：牛从迷宫走出来最多需要多少步。迷宫是用字符构造的，可能不止有一个出口，如这个宽5高3的迷宫，有两个出口，最远的格位于左下角，需9步走出。
+-+-+-+-+-+
|         |
+-+ +-+ + +
|     | | |
+ +-+-+ + +
| |     | 
+-+ +-+-+-+
多源最短路径问题。有几点需注意（在程序中体现）：
1. 如何处理输入，显然需要整行读入。不过要注意的是，第一行是表示宽度和高度的数字，读入以后，\n依然在io中，此时用第一个fgets读到的是个空行。
2. 如何表示格点和墙。一种方式用结构体，不方便。四个方向如何统一表示且统一从输入中得到，可以注意到，在输入串中墙的位置就是在格点的正确方向上。因而可以如程序中所示统一处理。
3. 多源最短路径，最简洁的方式，就是有多个起点的宽度优先搜索了，简单，也高效。

/*
ID: blackco3
TASK: maze1
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
#define _max_width_ 38
#define _max_height_ 100
#define _n_dir_ 4
int dw[_n_dir_]={0,0,1,-1}, dh[_n_dir_]={1,-1,0,0};
int n_wid, n_high ;
inline int out( int h, int w ){
	return h<0 || h==n_high || w<0 || w==n_wid ;
}
struct t_bfs_item {
	int high, wid, depth ;
} queue[_max_height_*_max_width_];

int main() {
	freopen("maze1.in", "r", stdin);
	freopen("maze1.out", "w", stdout);	 
	char grid_map[(_max_height_<<1)+1][(_max_width_+2)<<1];
	cin >> n_wid >> n_high ;
	fgets(grid_map[0], (_max_width_+2)<<1, stdin); /* redudent \n should be removed */
	for( int i=0; i<(n_high<<1)+1; i++ )
		fgets(grid_map[i], (_max_width_+2)<<1, stdin);
	int walls[_max_height_][_max_width_][_n_dir_], vis[_max_height_][_max_width_] ;
	t_bfs_item *p_tail = queue ;
	for( int h=0; h<n_high; h++ )
		for( int w=0; w<n_wid; w++ ){
			vis[h][w]=0 ;
			for( int dir=0; dir<_n_dir_; dir++ ){
				walls[h][w][dir] = grid_map[(h<<1)+1+dh[dir]][(w<<1)+1+dw[dir]]!=' ' ;
				if( out( h+dh[dir], w+dw[dir] ) && !walls[h][w][dir] )
					p_tail->wid=w, p_tail->high=h, p_tail->depth=1, p_tail++, vis[h][w]=1 ;
			}
		}
	int max_depth=0 ;
	for( t_bfs_item *p_head=queue; p_head!=p_tail; p_head++ ){
		max_depth = p_head->depth ;
		for( int dir=0; dir<_n_dir_; dir++ ){ 
			register int ch=p_head->high+dh[dir], cw=p_head->wid+dw[dir] ;
			if( out(ch, cw) || walls[p_head->high][p_head->wid][dir] || vis[ch][cw] )
				continue ;
			p_tail->wid=cw, p_tail->high=ch, p_tail->depth=max_depth+1, p_tail++, vis[ch][cw]=1 ;
		}
	}
	cout << max_depth << endl ;
	return 0;
}