SRM 541 Div2 1000pt : NonXorLife

問題概要＝解法

幅優先探索で距離K以下のマスの個数を求める問題。
簡単に感じられたけど、Div 2の正解者はかなり少なかった。

acceptされたコード

#include <vector>
#include <string>
#include <queue>
using namespace std;

const int MAX_K = 1500;

const int dy[] = {0, 0, 1, -1}, dx[] = {1, -1, 0, 0};

int dist[2*(MAX_K+100)][2*(MAX_K+100)];
bool visited[2*(MAX_K+100)][2*(MAX_K+100)];

struct NonXorLife {

	int countAliveCells(vector <string> field, int K) {
		queue< pair<int,int> > que;

		for(int i=0; i<(int)field.size(); ++i){
			for(int j=0; j<(int)field[i].length(); ++j){
				if(field[i][j] == 'o'){
					visited[i+MAX_K][j+MAX_K] = true;
					que.push(make_pair(i+MAX_K, j+MAX_K));
				}
			}
		}

		for(;!que.empty();){
			int y = que.front().first, x = que.front().second;
			que.pop();

			if(dist[y][x] == K){
				break;
			}
			for(int k=0; k<4; ++k){
				int ny = y + dy[k], nx = x + dx[k];
				if(!visited[ny][nx]){
					visited[ny][nx] = true;
					dist[ny][nx] = dist[y][x] + 1;
					que.push(make_pair(ny, nx));
				}
			}
		}

		int ans = 0;
		for(int i=0; i<2*(MAX_K+100); ++i){
			for(int j=0; j<2*(MAX_K+100); ++j){
				if(visited[i][j]){
					++ans;
				}
			}
		}
		return ans;
	}

};