记录编号	22794	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 激光电话	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2010-12-26 21:59:48	内存使用	2.54 MiB

/* 洪水填充: O(N^3) */
#include <fstream>
#include <queue>

#define MAXN 100

using namespace std;

struct Point
{
	int x,y;
} p[2];

const int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int n,m,mark[MAXN][MAXN],cnt;
char mat[MAXN][MAXN];

// 输入
void readFile(char *inpFile)
{
	ifstream f(inpFile);
	f >> m >> n;
	int k=0;
	for (int i=0; i<n; i++)
		for (int j=0; j<m; j++)	
		{
			f >> mat[i][j];
			if (mat[i][j]=='C') p[k].y=i,p[k++].x=j;
		}
	f.close();
}

// 输出
void writeFile(char *outFile)
{
	ofstream f(outFile);
	f << cnt-1 << "\n";
	f.close();
}

// 洪水填充
void floodfill()
{
	mark[p[0].y][p[0].x]=1;		// 从第一只牛开始
	queue<Point> q;
	q.push(p[0]);

	for ( ; ; )
	{
		Point pt=q.front();
		q.pop();
		cnt=mark[pt.y][pt.x];
		
		for (int k=0; k<4; k++)
			// 用一个方向填充
			// 弹出所有点直到遇见石头
			for (int i=pt.y+d[k][0],j=pt.x+d[k][1]; i>=0 && j>=0 && i<n &&
j<m; i+=d[k][0],j+=d[k][1])
			{
				if (mat[i][j]=='*') break;
				if (!mark[i][j])
				{ 
					mark[i][j]=cnt+1;		// 洪水填充已标记的图 (marker matrix)
									// 	记录最小的镜子数
									//	更新当前位置至 i,j
					Point pn;
					pn.y=i, pn.x=j;
					q.push(pn);
				}
				if (i==p[1].y && j==p[1].x) return;	// 遇到第二只牛结束
			}
	}
}

int main()
{
	readFile("lphone.in");
	floodfill();
	writeFile("lphone.out");
}