象棋 UVa1589

Posted by 尹傲雄 on March 27, 2017   

  看到这个题目基本的想法是,将黑将能走的四个方向都遍历一遍,然后再判断判断红方能否吃掉它。如果所有可能的走向都会被将死,则黑将被将死。需要注意越界,吃子,和马被别脚的情况。附上一张自己画的一张简图可能会清楚一些:   思路导图 下面贴一下代码,更详细的解释在代码的注释里,代码有点冗长,有能力的可以把相同的地方写成函数(比如说帅和车的判断是可以放一起的)

#include<iostream>
#include<fstream>
using namespace std;
struct qizhi
{
	char kind;
	int row;
	int column;
};

int panduan(int b_row, int b_column, int size, const qizhi*  p)   //用来判断黑将走某一步会不会被将死,如果会死返回0,不会返回1
{
	for (int i = 0; i < size; ++i)
	{
		switch (p[i].kind)
		{
		case 'G':
			if (p[i].column == b_column)
			{
				int key = 0;   //标记,
				for (int j = 0; j < size; ++j)    //如果黑将和红帅在同列,判断中间有没有其他的旗子
				{
					if (j == i)
						continue;
					if (p[j].column == p[i].column&&p[j].row > b_row&&p[j].row < p[i].row)
					{
						key = 1;
						break;
					}
				}
				if (0 == key)
					return 0;            //如果key为0,表面被将死直接返回0
			}
			break;
		case 'R':
			if (p[i].column == b_column)
			{
				int key = 0, key1;   //标记,
				p[i].row > b_row ? key1 = 1 : key1 = 0;
				for (int j = 0; j < size; ++j)    //如果黑将和车在同列,判断中间有没有其他的旗子
				{
					if (j == i)
						continue;
					if (key1 == 1)
					{
						if (p[j].column == p[i].column&&p[j].row > b_row&&p[j].row < p[i].row)
						{
							key = 1;
							break;
						}
					}
					else
					{
						if (p[j].column == p[i].column&&p[j].row <b_row&&p[j].row > p[i].row)
						{
							key = 1;
							break;
						}
					}

				}
				if (0 == key)
					return 0;            //如果key为0,表明被将死直接返回0
			}
			if (p[i].row == b_row)
			{
				int key = 0, key1;   //标记,
				p[i].column > b_column ? key1 = 1 : key1 = 0;
				for (int j = 0; j < size; ++j)    //如果黑将和车在同行,判断中间有没有其他的旗子
				{
					if (j == i)
						continue;
					if (key1 == 1)
					{
						if (p[j].row == p[i].row&&p[j].column > b_column&&p[j].column < p[i].column)
						{
							key = 1;
							break;
						}
					}
					else
					{
						if (p[j].row == p[i].row&&p[j].column < b_column&&p[j].column > p[i].column)
						{
							key = 1;
							break;
						}
					}

				}
				if (0 == key)
					return 0;            //如果key为0,表明被将死直接返回0
			}
			break;
		case 'C':
			if (p[i].column == b_column)
			{
				int key = 0, key1;   //标记,
				p[i].row > b_row ? key1 = 1 : key1 = 0;
				for (int j = 0; j < size; ++j)    //如果黑将和炮在同列,判断中间有多少个旗子
				{
					if (j == i)
						continue;
					if (1 == key1)
					{
						if (p[j].column == p[i].column&&p[j].row > b_row&&p[j].row < p[i].row)
						{
							key += 1;
						}
					}
					else
					{
						if (p[j].column == p[i].column&&p[j].row<b_row&&p[j].row>p[i].row)
						{
							key += 1;
						}
					}

				}
				if (1 == key)
					return 0;            //如果key为1,表明被将死直接返回0
			}
			if (p[i].row == b_row)
			{
				int key = 0, key1;   //标记,
				p[i].column > b_column ? key1 = 1 : key1 = 0;
				for (int j = 0; j < size; ++j)    //如果黑将和炮在同行,判断中间有多少个旗子
				{
					if (j == i)
						continue;
					if (1 == key1)
					{
						if (p[j].row == p[i].row&&p[j].column > b_column&&p[j].column < p[i].column)
						{
							key += 1;
						}
					}
					else
					{
						if (p[j].row == p[i].row&&p[j].column<b_column&&p[j].column>p[i].column)
						{
							key += 1;
						}
					}
				}
				if (1 == key)
					return 0;            //如果key为1,表明被将死直接返回0
			}
			break;
		 case 'H':
			int up = 0, down = 0, left = 0, right = 0;
			for (int j = 0; j < size; ++j)    //判断向上是否会别马脚
			{
				if (j == i)
					continue;
				if (p[j].row == p[i].row - 1 && p[j].column == p[i].column)
				{
					up = 1;
					break;                          //如果别马脚,就结束
				}
			}
			if (0 == up)
			{
				if (p[i].column - 1 == b_column&&p[i].row - 2 == b_row)
					return 0;
				else if (p[i].column + 1 == b_column&&p[i].row - 2 == b_row)
					return 0;
			}
			for (int j = 0; j < size; ++j)    //判断向左是否会别马脚
			{
				if (j == i)
					continue;
				if (p[j].row == p[i].row && p[j].column == p[i].column - 1)
				{
					left = 1;
					break;                          //如果别马脚,就结束
				}
			}
			if (0 == left)
			{
				if (p[i].column - 2 == b_column&&p[i].row - 1 == b_row)
					return 0;
				else if (p[i].column - 2 == b_column&&p[i].row + 1 == b_row)
					return 0;
			}
			for (int j = 0; j < size; ++j)    //判断向右是否会别马脚
			{
				if (j == i)
					continue;
				if (p[j].row == p[i].row && p[j].column == p[i].column + 1)
				{
					right = 1;
					break;                          //如果别马脚,就结束
				}

			}
			if (0 == right)
			{
				if (p[i].column + 2 == b_column&&p[i].row - 1 == b_row)
					return 0;
				else if (p[i].column + 2 == b_column&&p[i].row + 1 == b_row)
					return 0;
			}
			for (int j = 0; j < size; ++j)    //判断向下是否会别马脚
			{
				if (j == i)
					continue;
				if (p[j].row == p[i].row + 1 && p[j].column == p[i].column)
				{
					down = 1;
					break;                          //如果别马脚,就结束
				}

			}
			if (0 == down)
			{
				if (p[i].column - 1 == b_column&&p[i].row + 2 == b_row)
					return 0;
				else if (p[i].column + 1 == b_column&&p[i].row + 2 == b_row)
					return 0;
			}
			break;


		}
	}
	return 1;
}

int yes_or_no(int b_row, int b_column, int size, qizhi*  p)               //判断有没有被将死,将死返回false,没死返回true
{
	int up = 0, down = 0, left = 0, right = 0;
	if (b_row - 1 > 0)                         //判断向上走会不会死
	{
		for (int i = 0; i < size; ++i)
		{
			if (p[i].column == b_column&&p[i].row == b_row - 1)      //判断黑将去的地方有没有红棋的子如果有吃掉
			{
				p[i].kind = ' ';
				break;
			}
		}
		up = panduan(b_row - 1, b_column, size, p);
	}
	if (b_row + 1 < 4)                                   //判断向下走会不会死
	{
		for (int i = 0; i < size; ++i)
		{
			if (p[i].column == b_column&&p[i].row == b_row + 1)      //判断黑将去的地方有没有红棋的子如果有吃掉
			{
				p[i].kind = ' ';
				break;
			}
		}
		down = panduan(b_row + 1, b_column, size, p);
	}
	if (b_column - 1 > 3)								//判断向左走会不会死
	{
		for (int i = 0; i < size; ++i)
		{
			if (p[i].column == b_column - 1 && p[i].row == b_row)      //判断黑将去的地方有没有红棋的子如果有吃掉
			{
				p[i].kind = ' ';
				break;
			}
		}
		left = panduan(b_row, b_column - 1, size, p);
	}
	if (b_column + 1 < 7)                       //判断向右走会不会死
	{
		for (int i = 0; i < size; ++i)
		{
			if (p[i].column == b_column + 1 && p[i].row == b_row)      //判断黑将去的地方有没有红棋的子如果有吃掉
			{
				p[i].kind = ' ';
				break;
			}
		}
		right = panduan(b_row, b_column + 1, size, p);
	}
	return up + down + left + right;
}

int main()
{
	///*文件重定向,输出测试*/
	//ifstream fin;
	//fin.open("data.in");
	//cin.rdbuf(fin.rdbuf());
	//ofstream out;
	//out.open("data.out");
	//cout.rdbuf(out.rdbuf());
	int r_number = 0, b_row = 0, b_column = 0;        //红方棋字个数,黑方将的位置
	while (cin >> r_number >> b_row >> b_column&&r_number != 0 && b_column != 0 && b_row != 0)
	{
		auto p = new qizhi[r_number];
		for (int i = 0; i < r_number; ++i)
		{
			cin >> p[i].kind >> p[i].row >> p[i].column;
		}
		if (yes_or_no(b_row, b_column, r_number, p))
			cout << "NO" << endl;
		else
			cout << "YES" << endl;
		delete[] p;

	}


}

  前面的题目的一些代码在gihub的仓库里https://github.com/YinAoXiong/Algorithmic-exercises,(全部都是用vs2015写的工程文件,源文件在同名的子目录目录中)


知识共享许可协议
作品尹傲雄采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。