记录编号	176851	评测结果	AAAAAAAAAA
题目名称	130.[USACO Mar08] 游荡的奶牛	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2015-08-10 07:27:42	内存使用	1.24 MiB

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>

#define MAXN 101UL

using namespace std;

int n,m,t;

int gx[4] = {-1,0,1,0};
int gy[4] = {0,1,0,-1};

struct Node {
	int x,y,step;
};

int f[MAXN][MAXN][18];
bool z[MAXN][MAXN][18];
int map[MAXN][MAXN];
char a[MAXN][MAXN];
int chu_x,chu_y;
int zd_x,zd_y;
queue<Node> q;

void bfs() {
	while(!q.empty()) {
		Node ai = q.front();
		q.pop();
		z[ai.x][ai.y][ai.step] = 0;
		for(int i = 0; i < 4; ++i) {
			int qx = ai.x + gx[i];
			int qy = ai.y + gy[i];
			int qstep = ai.step+1;
			if(qx < 1 || qx > n) continue;
			if(qy < 1 || qy > m) continue;
			if(map[qx][qy] == 1) continue;
			f[qx][qy][qstep] += f[ai.x][ai.y][ai.step];
			if(qstep >= t) continue;
			if(z[qx][qy][qstep]) continue;
			z[qx][qy][qstep] = 1;
			Node pos;
			pos.x = qx;
			pos.y = qy;
			pos.step = qstep;
			q.push(pos);
		}
	}

}

int main() {
	int i,j;
	freopen("ctravel.in","r",stdin);
	freopen("ctravel.out","w",stdout);
	cin >> n >> m >> t;
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= m; ++j) {
			cin >> a[i][j];
		}
	cin >> chu_x >> chu_y >> zd_x >> zd_y;
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= m; ++j) {
			if(a[i][j] == '.')
				map[i][j] = 0;
			if(a[i][j] == '*')
				map[i][j] = 1;
		}
	Node temp;
	temp.x = chu_x;
	temp.y = chu_y;
	temp.step = 0;
	f[chu_x][chu_y][0] = 1;
	z[chu_x][chu_y][0] = 1;
	q.push(temp);
	bfs();
	cout << f[zd_x][zd_y][t];
}