neoevoke » [usaco] 2.4 Overfencing

[usaco] 2.4 Overfencing - usaco

2009.08.24 00:25 neoevoke Edit

해석을 매끄럽고 깔끔하게 하지 못해 빨리 풀지 못했다.
더 집중해서 잘 읽어보자.

문제는 쉬운문제다. 미로의 모든 점에서 (가장 가까운 출구까지 거리)가 가장 먼 거리를 출력하는 것이다.

모든 점에 대해서 queue로 돌려보면 된다.

/*
ID: neoevok1
PROG: maze1
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int w,h;
int m[210][100];
int sx=-1,sy=-1,ex,ey;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int v[210][100];

int find(int y, int x)
{
	queue<pair<pair<int, int>,int> > q;
	q.push(make_pair(make_pair(y,x),1));
	int cnt=0;
	while(!q.empty())
	{
		int y=q.front().first.first;
		int x=q.front().first.second;
		v[y][x]=1;
		cnt=q.front().second;
		q.pop();
		if(y==ey && x==ex) break;
		if(y==sy && x==sx) break;
		for(int i=0;i<4;i++)
		{
			if(m[y+dy[i]][x+dx[i]]==0)
			{
				if(v[y+dy[i]*2][x+dx[i]*2]==0)
				{
					v[y+dy[i]*2][x+dx[i]*2]=1;
					q.push(make_pair(make_pair(y+dy[i]*2,x+dx[i]*2),cnt+1));
				}
			}
		}
	}
	return cnt;
}

int main() {
    ofstream fout ("maze1.out");
    ifstream fin ("maze1.in");

fin  >> w >> h;
		string tmp;
	fin.ignore();
	for(int i=0;i<h*2+1;i++)
	{
		getline(fin, tmp);
		for(int j=0;j<w*2+1;j++)
		{
			if(tmp[j]==' ')
				m[i][j]=0;
			else
				m[i][j]=1;
		}
	}
	for(int i=0;i<h*2;i++)
	{
		if(m[i][0]==0)
			if(sx==-1)
			{
				sx=1;
				sy=i;
			}
			else
			{
				ex=1;
				ey=i;
			}
		if(m[i][2*w]==0)
			if(sx==-1)
			{
				sx=2*w-1;
				sy=i;
			}
			else
			{
				ex=2*w-1;
				ey=i;
			}
	}
	for(int i=0;i<w*2;i++)
	{
		if(m[0][i]==0)
			if(sx==-1)
			{
				sx=i;
				sy=1;
			}
			else
			{
				ex=i;
				ey=1;
			}
		if(m[2*h][i]==0)
			if(sx==-1)
			{
				sx=i;
				sy=2*h-1;
			}
			else
			{
				ex=i;
				ey=2*h-1;
			}
	}

int cnt=0;
	for(int y=1;y<2*h;y+=2)
		for(int x=1;x<2*w;x+=2)
		{
			memset(v,0,sizeof(v));
			cnt=max(cnt,find(y,x));
		}

fout << cnt << endl;

return 0;
}

Perfect balanced KDTree * Pacific Northwestsern Regional 2008

Trackbacks 0

엮인글 주소: http://dw.yutar.net/329429/e61/trackback

Comments 0

Leave Comments

neoevoke난 전설 같은건 믿지 않아

[usaco] 2.4 Overfencing - usaco

Trackbacks 0

Comments 0

Leave Comments

Category

Recent Post

Recent Comment

Recent Trackback

Tag