글 읽기 - 시간 초과 도와주세요

ojh031 4년 전 0

질문에 있는 글을 보고 다시 아래처럼 풀어봤습니다

그런데 시간초과가 나네요..

제 생각으로는 원상태로 배열을 돌려준 후 다시 시작해야만 빈 공간 없이 모두 확인할 수 있다고 생각해서 저렇게 작성했는데 저거보다 효율적으로 하는 방법이 무엇이 있을지 너무 감이 안잡힙니다..

include <iostream>

using namespace std;

int N,M;
int L,R;
char ways[1001][1001];
bool visit[1001][1001];
int lands=0;
int startX;
int startY;

void dfs(int x,int y){
	if((ways[x][y-1]=='0' ||ways[x][y-1]=='3') && !visit[x][y-1] && L>0){
		visit[x][y-1]=true;
		L-=1;
		ways[x][y-1]='3';
		dfs(x,y-1);
		visit[x][y-1]=false;
		L++;
	}
	if((ways[x][y+1]=='0' || ways[x][y+1]=='3') && !visit[x][y+1] && R>0){
		visit[x][y+1]=true;
		ways[x][y+1]='3';
		R-=1;
		dfs(x,y+1);
		visit[x][y+1]=false;
		R++;
	}
	
	if((ways[x+1][y]=='0' || ways[x+1][y]=='3') && !visit[x+1][y]){
		visit[x+1][y]=true;
		ways[x+1][y]='3';
		dfs(x+1,y);
		visit[x+1][y]=false;
	}
	
	if((ways[x-1][y]=='0' || ways[x-1][y]=='3') && !visit[x-1][y]){
		visit[x-1][y]=true;
		ways[x-1][y]='3';
		dfs(x-1,y);
		visit[x-1][y]=false;
	}

}
void input(){
	cin>>N>>M>>L>>R;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			cin>>ways[i][j];
			visit[i][j]=false;
			if(ways[i][j]=='2'){
				startX=i;
				startY=j;
			}
		}
	}
}

void output(){
	int count=1;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			if(ways[i][j]=='3')
				count++;
		}
	}
	cout<<count<<endl;
}
int main(){
	input();
	dfs(startX,startY);
	output();
	return 0;
}

nahwasa 4년 전 1

힌트는 '위, 아래로는 얼마든지' 입니다!

ojh031 4년 전 1

@nahwasa 감사합니다! 말씀하신대로만 하니까 해결이 됐습니다.. 근데 그 이유를 잘 모르겠습니다

비슷한 문제가 있다면 풀어보고 확실히 이해를 해야겠네요.. 저희 학교 선배님이신 것 같은데 정말 감사드립니다.

nahwasa 4년 전 0

비슷한게 있었는데...

못찾겠어요.. 낼 찾으면 알려드릴꼐요!

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

문제

문제

출처

ICPC

시간 초과 도와주세요

ojh031 4년 전 0

nahwasa 4년 전 1

ojh031 4년 전 1

nahwasa 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말