Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/05/28

TopCoder Open 2010 Algorithm Qualification Round 3

| 16:31

http://www.topcoder.com/stat?c=problem_statement&pm=10929&rd=14278

問題

横 W 縦 H の芝生をダイアモンドカッターが切っていく.カッターの初期位置と,移動方向のプログラムが与えられたときに,芝生が何分割されているかを答える.

アプローチ

ある位置の芝生の左が切れているかどうかのフラグと上が切れているかどうかのフラグを用意しておき,プログラムを走らせて切っていき,最後に領域を数える.

領域を数えるのは再帰スタック,深さ優先)だと最悪 10^6 になるのでオーバーフローする.queue を使って幅優先探索を行う.

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <queue>

using namespace std;

typedef pair<int,int> PII;

#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define Forall(i,v)   for(int i=0;i<(int)v.size();++i)
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

bool cutu[1024][1024];
bool cutl[1024][1024];
bool glass[1024][1024];

queue<PII> q;

int pieces(int W, int H, int startx, int starty, vector <string> program)
{
	Rep(j,H+1) Rep(i,W+1)
		cutu[j][i] = cutl[j][i] = glass[j][i] = false;
	Rep(i,W+1)
		cutu[0][i] = cutu[H][i] = true;
	Rep(j,H+1)
		cutl[j][0] = cutl[j][W] = true;
	
	int x = startx;
	int y = starty;
	
	Rep(pp,sz(program)) Rep(p,sz(program[pp]))
	{
		switch(program[pp][p])
		{
		case 'U':
			cutl[--y][x] = true;
			break;
		case 'D':
			cutl[y++][x] = true;
			break;
		case 'L':
			cutu[y][--x] = true;
			break;
		case 'R':
			cutu[y][x++] = true;
			break;
		}
	}
	
	int c = 0;
	Rep(j,H) Rep(i,W) if(!glass[j][i])
	{
		c++;
		q.push(mp(i,j));
		while(!q.empty())
		{
			PII co = q.front(); q.pop();
			int x = co.first;
			int y = co.second;
			if(glass[y][x])
				continue;
			glass[y][x] = true;
			if(!cutu[y][x])   q.push(mp(x,y-1));
			if(!cutu[y+1][x]) q.push(mp(x,y+1));
			if(!cutl[y][x])   q.push(mp(x-1,y));
			if(!cutl[y][x+1]) q.push(mp(x+1,y));
		}
	}
	
	return c;
}

DiegoDiego2012/07/10 00:56The pucrahses I make are entirely based on these articles.

rcomsiercomsie2012/07/10 15:55WkGRgf <a href="http://ndjqpxpaabuy.com/">ndjqpxpaabuy</a>

lurhlpgihxdlurhlpgihxd2012/07/10 21:512sAKJD , [url=http://wyqyxabtrpox.com/]wyqyxabtrpox[/url], [link=http://fetlavsdhbsq.com/]fetlavsdhbsq[/link], http://frjyegfwmtje.com/

sxyqsmsxyqsm2012/07/12 12:11UCCj2u <a href="http://srlypizeryby.com/">srlypizeryby</a>