记录编号	177206	评测结果	AAAAAAAAAA
题目名称	[NOIP 2002]过河卒	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2015-08-11 11:40:23	内存使用	0.28 MiB

#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

const int MAX(21), DX[2] = {0, 1}, DY[2] = {1, 0};
int n, m, a[MAX][MAX] = {0}, hx, hy;
bool pd[MAX][MAX] = {true};
ifstream fin("pj024.in");
ofstream fout("pj024.out");
#define cin fin
#define cout fout
queue<pair<int, int> > q;
inline void bfs();

main()
{
	cin >> n >> m >> hx >> hy;
//	cout << n << m << endl;
	fin.close();
	
	for (int i = 0; i <= n; ++i)
		fill(pd[i] + 0, pd[i] + m + 1, false);
	pd[hx][hy] = 1;
	if (hx - 2 >= 0 && hy - 1 >= 0)
		pd[hx - 2][hy - 1] = true;
	if (hx - 2 >= 0 && hy + 1 <= m)
		pd[hx - 2][hy + 1] = 1;
	if (hx - 1 >= 0 && hy - 2 >= 0)
		pd[hx - 1][hy - 2] = 1;
	if (hx - 1 >= 0 && hy + 2 <= m)
		pd[hx - 1][hy + 2] = 1;
	if (hx + 1 <= n && hy - 2 >= 0)
		pd[hx + 1][hy - 2] = 1;
	if (hx + 1 <= n && hy + 2 <= m)
		pd[hx + 1][hy + 2] = 1;
	if (hx + 2 <= n && hy - 1 >= 0)
		pd[hx + 2][hy - 1] = 1;
	if (hx + 2 <= n && hy + 1 <= m)
		pd[hx + 2][hy + 1] = 1;
	a[0][0] = 1;
	pd[0][0] = 1;
	q.push(make_pair(0, 0));
	bfs();
	
	cout << a[n][m];
//	cout << endl;
//	for (int i = 0; i <= n; ++i){
//		for (int j = 0; j <= m; ++j)
//			cout << a[i][j] << ' ';
//		cout << endl;
//	}
//	for(;;);
}

inline void bfs(){
	while (! q.empty()){
		int ox = q.front().first, oy = q.front().second;
		q.pop();
		for (int i = 0; i < 2; ++i){
			int nx = ox + DX[i], ny = oy + DY[i];
			if (nx >= 0 && ny >= 0 && nx <= n && ny <= m){
				a[nx][ny] += a[ox][oy];
				if (! pd[nx][ny]){
					pd[nx][ny] = 1;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
}