글 읽기 - DFS인데 반례를 못 찾겠습니다 ㅜ

4whomtbts 6년 전 0

너무 생각나는데로 짜서 반례찾기가 더럽게 작성되었는데,

주어진 테스트케이스에는 맞는데, 도대체 반례가 뭐가 있는지 모르겠습니다 ㅜ

#include
#include

using namespace std;
int dir[5][3] = { 
{-1,0},{1,0},{0,1},{0,-1}
};

int i, j, k;
int a, b, c, d, e, f, g, l;
int testcase;
int n, m;

int map[60][60] = {0,};

int cnt = 0;
int width, height = 0;


bool isValid(int y, int x)
{
return (x >= 0 && x < width) && (y >= 0 && y < height);
}
void dfs(int y, int x,int count)
{
map[y][x] = 2;
if(count == 1)
{
cnt++;
}
for ( k = 0; k < 4; k++)
{
int dx = x + dir[k][0];
int dy = y + dir[k][1];

if ( isValid(dy,dx) && map[dy][dx] == 1)
{

dfs(dy, dx,0);
}
}


}

int main() {
int testcase = 0;
int cabbage = 0;
cin >> testcase;

while (testcase--){
cin >> width >> height >> cabbage;
for ( i = 0; i < height; i++){
for( j = 0; j < width; j++){
map[i][j] = 0;

}
}

for ( i = 0; i < cabbage; i++)
{
int x, y = 0;
cin >> y >> x;
map[y][x] = 1;
}

for ( i = 0; i < height; i++)
{
for ( j = 0; j < width; j++)
{

if ( map[i][j] == 1){
dfs(i, j, 1);
}

}
}
	
	cout << cnt<<endl;
	cnt = 0;
	}

	return 0;

}

djm03178 6년 전 0

배추의 좌표는 가로부터 주어지는데 세로부터 입력받고 있습니다.

그리고 들여쓰기를 하는 습관을 들이시길 권장합니다.

4whomtbts 6년 전 0

아아 감사합니다, 들여쓰기는 VS 에서 하는데 복붙하니깐 없어지드라구요 ㅋㅋ

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

문제

문제

출처

ICPC

DFS인데 반례를 못 찾겠습니다 ㅜ

4whomtbts 6년 전 0

djm03178 6년 전 0

4whomtbts 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말