UVa : 11906 (Knight in War Grid)



some points: 

1. if you can not go anywhere else, still the output is: Case 1: 1 0
because square (0, 0) is marked even 

2. Take care of the case where either M or N is 0, or when M = N. 
There are only 4 possible movements (compared to 8) for these cases. 
(Src: http://www.algorithmist.com/index.php/UVa_11906)

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long

inline LL Power(int b, int p) { LL ret = 1; for ( int i = 1; i <= p; i++ ) ret *= b; return ret; }

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(i, x) for(typeof (x.begin()) i = x.begin(); i != x.end (); i++)
#define Set(a, s) memset(a, s, sizeof (a))
#define max(a, b)  (a < b ? b : a)
#define min(a, b)  (a > b ? b : a)

using namespace std;

int r, c, m, n, w;
int mat [100 + 2] [100 + 2];

void print (int r, int c) {

	for ( int i = 0; i < r; i++ ) {
		for ( int j = 0; j < c; j++ ) {
			printf (" %d ", mat [i] [j]);
		}
		printf ("\n");
	}

	printf ("\n\n");
}

int main ()
{
	int testCases; scanf ("%d", &testCases);
	int cases = 0;

	while ( testCases-- ) {

		Set(mat, 0);
		
		scanf ("%d %d %d %d", &r, &c, &m, &n);
		scanf ("%d", &w);

		map < pair<int, int>, bool > waterMap;

		for ( int i = 0; i < w; i++ ) {
			int a, b; scanf ("%d %d", &a, &b);
			waterMap [make_pair(a, b)] = true;
		}
		
		queue <pair<int, int> > q;
		q.push(make_pair(0, 0));

		map <pair<int, int>, bool> visited;
		visited [make_pair(0, 0)] = true;

		mat [0] [0] = 0;
		
		int dr [] = {-m, -m, m, m, -n, n, -n, n};
		int dc [] = {n, -n, n, -n, m, m, -m, -m};

		while (!q.empty()) {
			pair<int, int> pop = q.front (); q.pop();

			int newX, newY;
			set<pair<int, int> > distinct;

			for ( int i = 0; i < 8; i++ ) {
				newX = dr [i] + pop.first;
				newY = dc [i] + pop.second;

				distinct.insert(make_pair(newX, newY));
			}

			for (set<pair<int, int> >::iterator it = distinct.begin(); it != distinct.end(); it++ ) {
				pop = *it;
				newX = pop.first;
				newY = pop.second;
				
				if ( newX >= 0 && newX < r && newY >= 0 && newY < c && !waterMap [make_pair(newX, newY)]) {
					mat [newX] [newY]++;

					if ( !visited [make_pair(newX, newY)] ) {
						visited [make_pair(newX, newY)] = true;
						q.push(make_pair(newX, newY));
					}
					

				}
			}

			//print (r, c);
		}

		int cntEven = 0, cntOdd = 0;

		for ( int i = 0; i < r; i++ ) {
			for ( int j = 0; j < c; j++ ) {
				if ( mat [i] [j] || ( !i && !j ) ) {
					if ( mat [i] [j] % 2 ) cntOdd++;
					else cntEven++;
				}
			}
		}

		printf ("Case %d: %d %d\n", ++cases, cntEven, cntOdd);
	}

	return 0;
}

// @END_OF_SOURCE_CODE

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s