Submission #528119

---

Source Code Expand

/*{{{*/
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
typedef int8_t sbyte;
typedef uint8_t byte;
typedef uint16_t ushort;
typedef uint32_t uint;
typedef int64_t i64;
typedef uint64_t u64;
template<class T> static inline T ABS(T x) {return x < 0 ? -x : x;}
template<class T> static inline void MAZ(T &a, const T &b) {if(a < b) a = b;}
template<class T> static inline void MIZ(T &a, const T &b) {if(b < a) a = b;}
/*}}}*/
static i64 Inv(i64 x, i64 m) {//1<=x<m ; GCD(x,m)=1 ; m(m-2)+1 \in long long
	return x == 1 ? 1 : ((i64)(x - Inv(m % x, x)) * m + 1) / x;
}

static const auto MOD = 1000000009;
static const auto HMAX = 16;
static const auto WMAX = 16;
static const auto NMAX = HMAX * WMAX;

static int N;
static int A[NMAX][NMAX];

static int solve() {
	auto ret = (i64)1;
	for(auto i = 0; i < N; i++) {
		auto j = i;
		for(; j < N && A[j][i] == 0; j++);
		if(j == N) return 0;
		if(j != i) {
			for(auto k = i; k < N; k++) swap(A[i][k], A[j][k]);
			ret = MOD - ret;
		}
		for(j = i + 1; j < N; j++) {
			if(A[j][i] == 0) continue;
			auto x = A[j][i] * Inv(A[i][i], MOD) % MOD;
			for(auto k = i; k < N; k++) {
				A[j][k] = (A[j][k] - A[i][k] * x) % MOD;
				if(A[j][k] < 0) A[j][k] += MOD;
			}
		}
	}
	for(auto i = 0; i < N; i++) ret = ret * A[i][i] % MOD;
	return ret;
}

static void input() {
	static const int dir[2][2] = {{-1, 0}, {0, -1}};
	static char M[HMAX][WMAX + 1];
	static int  Z[HMAX][WMAX];
	int H, W;
	scanf("%d%d", &H, &W);
	for(auto i = 0; i < H; i++) scanf("%s", M[i]);
	for(auto i = 0; i < H; i++) {
		for(auto j = 0; j < W; j++) {
			if(M[i][j] != 'W') continue;
			Z[i][j] = N++;
			for(auto k = 0; k < 2; k++) {
				auto ii = i, jj = j;
				for(; ; ) {
					if((ii += dir[k][0]) < 0) break;
					if((jj += dir[k][1]) < 0) break;
					if(M[ii][jj] == 'W') {
						auto a = N - 1, b = Z[ii][jj];
						A[a][b] = MOD - 1;
						A[a][a]++;
						A[b][a] = MOD - 1;
						A[b][b]++;
						break;
					}
				}
			}
		}
	}
}

int main() {
	input();
	N--;
	printf("%d\n", solve());
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void input()’:
./Main.cpp:76:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &H, &W);
                       ^
./Main.cpp:77:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(auto i = 0; i < H; i++) scanf("%s", M[i]);
                                               ^

Judge Result