글 읽기 - [c++] 저의 멍청함 지적해주실분.........

yejun0157 1년 전 1

단순한 dfs 로 문제를 풀었는데 예제 2가 안 나오네요. 도대체 무엇이 문제인가요?

#include<iostream>
#include<string>
using namespace std;
string s[1001];
bool ans=false;
int elec[1001][1001]={0};
int visit[1001][1001]={0};
int dh[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int m, n;
void dfs(int h,int y)
{
	visit[h][y]=1;
	for (int i=0;i<4;i++)
	{
		int th=h+dh[i];
		int ty=y+dy[i];
		if (0<=th&&th<m)
		{
			if (0<=ty&&ty<n)
				if (elec[th][ty]==0&&visit[th][ty]==0)
					dfs(th,ty);
		}
	}
}
void reset()
{
	for (int i=0;i<m;i++)
	{
		for  (int j=0;j<n;j++)
			visit[i][j]=0;
	}
}
int main(int argc, char** argv) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>m>>n;
	for (int i=0;i<m;i++)
	{
		cin>>s[i];
		for (int j=0;j<n;j++)
			elec[i][j]=s[i][j]-'0'; 
	}
	for (int i=0;i<n;i++)
	{
		reset();
		if (elec[0][i]==0&&visit[0][i])
			dfs(0, i);
		for (int j=0;j<n;j++)
		{
			if (visit[m-1][i]==1)
			{
				ans=true;
				break;
			}
		}
		if (ans)
		{
			cout<<"YES";
			return 0;
		}
	}
	cout<<"NO";
	return 0;
}

rmstjd23 1년 전 1

47번 라인 조건문에서

visit[0][i] 를 체크하시는데, 처음 탐색을 시작할때 visit[0][i]는 어떤값이 들어있나요?

yejun0157 1년 전 1

처음엔 0이 들어있었네요! 그럼 아예 탐색을 안 하겠군요!!!! 그래서 아래와 같이 코드를 수정했는데 여전히 예제 2가 안 나오네요ㅠㅠㅠㅠ

#include<iostream>
#include<string>
using namespace std;
string s[1001];
bool ans=false;
int elec[1001][1001]={0};
int visit[1001][1001]={0};
int dh[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int m, n;
void dfs(int h,int y)
{
	visit[h][y]=1;
	for (int i=0;i<4;i++)
	{
		int th=h+dh[i];
		int ty=y+dy[i];
		if (0<=th&&th<m)
		{
			if (0<=ty&&ty<n)
				if (elec[th][ty]==0&&visit[th][ty]==0)
					dfs(th,ty);
		}
	}
}
void reset()
{
	for (int i=0;i<m;i++)
	{
		for  (int j=0;j<n;j++)
			visit[i][j]=0;
	}
}
int main(int argc, char** argv) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>m>>n;
	for (int i=0;i<m;i++)
	{
		cin>>s[i];
		for (int j=0;j<n;j++)
			elec[i][j]=s[i][j]-'0'; 
	}
	for (int i=0;i<n;i++)
	{
		reset();
		if (elec[0][i]==0&&!visit[0][i])
			dfs(0, i);
		for (int j=0;j<n;j++)
		{
			if (visit[m-1][i]==1)
			{
				ans=true;
				break;
			}
		}
		if (ans)
		{
			cout<<"YES";
			return 0;
		}
	}
	cout<<"NO";
	return 0;
}

kokosoko59 1년 전 1

51번줄 조건문에 j를 i 로 잘못쓰신것 같아요

yejun0157 1년 전 1

감사합니다! 덕분에 맞았어요!

rmstjd23, kokosoko59 감사합니다~~~~~~~~~~~~~~~~~~~`

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

문제

문제

출처

ICPC

[c++] 저의 멍청함 지적해주실분.........

yejun0157 1년 전 1

rmstjd23 1년 전 1

yejun0157 1년 전 1

kokosoko59 1년 전 1

yejun0157 1년 전 1

rmstjd23, kokosoko59 감사합니다~~~~~~~~~~~~~~~~~~~`

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말