Topcoder problem analysis - ChessCover (Inv 2001 Semi A+B 1000 pointer)

Problem statement
https://community.topcoder.com/stat?c=problem_statement&pm=202&rd=53

This turned out simpler than the 500 pointer, especially since I had the 2d iterator class. Piece of cake - didn't take more than 30 minutes to code.

---

Solution

	#include <bits/stdc++.h>
	#define mp make_pair
	#define vstr vector<string>
	#define pb push_back
	#define all(x) begin(x), end(x)
	#define sz(x) int(x.size())
	#define P(X) cout << X << "\t"
	#define NL cout << endl
	#define FOR(I,N) for(int I = 0; I < N; ++I)
	using namespace std;
	typedef pair<int, int> Coord;
	typedef pair<int, int> Incr;
	static constexpr Incr UP = mp(-1, 0), DN = mp(1, 0), LT = mp(0, -1), RT = mp(0, 1);
	static constexpr Incr NE = mp(-1, 1), NW = mp(-1, -1), SE = mp(1, 1), SW = mp(1, -1);
	template<typename T> struct Iter2d
	{
	// ... snip (See iter2d.cpp) ...
	};
	struct ChessCover
	{
	typedef Iter2d<char> Iter;
	void attack(vector<vector<char>> &board, const Coord &c, const std::initializer_list<Incr> dirs)
	{
	for(const auto &dir:dirs)
	for(Iter it = Iter(board, c, dir).next(), ite = it.end(); it != ite && (*it == 'U' || *it == '*'); ++it)
	*it = '*';
	}
	void attackOne(vector<vector<char>> &board, const Coord &c, std::initializer_list<Incr> dirs)
	{
	for(const auto &dir:dirs)
	{
	Iter it(board, c, dir);
	if(++it && *it == 'U') *it = '*';
	}
	}
	int getSafe(vector<string> param0)
	{
	vector<vector<char>> board;
	FOR(i, param0.size()) board.push_back(vector<char>(all(param0[i])));
	FOR(i, sz(board))
	FOR(j, sz(board[0]))
	{
	Coord c = mp(i, j);
	switch(board[i][j])
	{
	case 'Q': attack(board, c, {UP, DN, LT, RT, NE, NW, SE, SW}); break;
	case 'R': attack(board, c, {UP, DN, LT, RT}); break;
	case 'B': attack(board, c, {NE, NW, SE, SW}); break;
	case 'P': attackOne(board, c, {NE, NW, SE, SW}); break;
	case 'K':
	attackOne(board, c, {mp(-2, -1), mp(-1, -2), mp(-2, 1), mp(-1, 2),
	mp(2, -1), mp(1, -2), mp(2, 1), mp(1, 2)});
	break;
	}
	}
	int cnt = 0;
	FOR(i, sz(board))
	{
	cnt += count(all(board[i]), 'U');
	}
	return cnt;
	}
	};

view raw ChessCover.cpp hosted with ❤ by GitHub

The algorithm is really simple -

• We scan the chess board for pieces
• For each piece except knights and pawns we call attack(), passing an array of directions
• For knights and pawns we call attackOne()
• The attack() function iterates in each of the passed directions starting at that piece and marks the empty squares unsafe. It stops if any piece is encountered
• The attackOne() function does the same, but only one step instead of all the way

The fact that we had an iterator means, we don't have to care about the bounds of the board, or do anything differently for any direction.

Note the use of std::initializer_list to allow us to pass literal array constants to a function and treat them as a container (with zero runtime overhead)

This was one of the most satisfying bits of code I wrote so far in this series.