글 읽기 - 1000자리까지 계산은 할 수 없어서..

zzong0324 7년 전 0

1000자리까지 넣어볼 수는 없어서

대충 해봤는데.. 37%쯤에서 터집니다.. 어떤점을 제가 못보고 있는지 알려주시면 감사하겠습니다.(__)

#include <queue>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <math.h>
using namespace std;
int moving_x[4] = { 1,-1,0,0 };
int moving_y[4] = { 0,0,1,-1 };
bool visit[1001][1001];
int wall[1001][1001];

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			int a;
			scanf("%1d", &a);
			wall[i][j] = a;
		}
	}
	bool isbroke = false;		//부셨나?

	//이 문제는 부셨을때와 안부셨을때 두가지 경우를 모두 넣고 푼다.

	queue<pair<pair<int, int>,pair<int, bool>>> q;
	q.push(make_pair(make_pair(1, 1), make_pair(1,isbroke)));
	visit[1][1] = true;
	int ans = -1;
	while (!q.empty())
	{
		int cx = q.front().first.first;
		int cy = q.front().first.second;
		int cnt = q.front().second.first;
		bool isbroken = q.front().second.second;
		if (cx == n && cy == m)
		{
			ans = cnt;
			break;
		}
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = cx + moving_x[i];
			int ny = cy + moving_y[i];
			if (nx > 0 && nx <= n && ny > 0 && ny <= m)
			{
				//안부신다
				if (!visit[nx][ny] && wall[nx][ny] == 0)
				{
					visit[nx][ny] = true;
					q.push(make_pair(make_pair(nx, ny),make_pair(cnt+1, isbroken)));
				}

				//부신다.
				if (!visit[nx][ny] && wall[nx][ny] == 1 && !isbroken)
				{
					visit[nx][ny] = true;
					q.push(make_pair(make_pair(nx, ny), make_pair(cnt+1,true)));
					
				}
			}
			
		}
	}
	printf("%d\n", ans);
}

kdk8361 7년 전 3

6 4
0000
1110
0000
1111
0111
0000

zzong0324 7년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1000자리까지 계산은 할 수 없어서..

zzong0324 7년 전 0

kdk8361 7년 전 3

zzong0324 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말