글 읽기 - 반례를 못찾겠어용;

ghdtmdwo123 5년 전 0

반례를 못찾겠어용;;

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;


int main() {

	stack<pair<int,int>> S;
	//int B[51][51] = {(0,0)};
	int dy[4] = { 1,0,-1,0 }; // 오른쪽 아래 왼쪽 위
	int dx[4] = { 0,-1,0,1 };
	//bool V[51][51] = {(false,false)};
	int T;
	cin >> T;
	while (T--) {
		int M, N, K;
		int B[51][51] = { (0,0) };
		bool V[51][51] = { (false,false) };
		cin >> M >> N >> K;

		int count = 0;
		int c = 0;
		int d = 0;

		for (int i = 0; i < K; i++) {
			cin >> c >> d;
			B[c][d] = 1;
			//cout << c << "  " << d << "\n";
		}




		for (int i = 0; i < N; i++) { // y, 오른쪽, 왼쪽
			for (int j = 0; j < M; j++) { // x, 위 ,아래 

				if (B[i][j] == 1 && !V[i][j]) {							//1을 찾으면
					//cout << i << "  " << j << " 들어감" << "\n";
					count++;
					S.push({ i,j });
					while (!S.empty()) {
						auto cur = S.top();
						S.pop();
						//cout << cur.first << "  " << cur.second << " 스택" << "\n";
						for (int k = 0; k < 4; k++) { // 현재 위치에서 여러곳 1찾음

							int y = cur.first + dy[k]; //int dy[4] = { 1,0,-1,0 }; // 오른쪽 아래 왼쪽 위
							int x = cur.second + dx[k]; //int dx[4] = { 0,-1,0,1 };
							if ((y > -1 && y < N && x < M && x > -1) && (!V[y][x] && B[y][x])) {
								//cout << y << "  " << x << " 너추가" << "\n";
								V[y][x] = 1;
								S.push({ y,x });

							}

						}
					}
				}


			}
		}
		
		cout << count;
		//if(T != 0) cout << "\n";
	}
}

evenharder 5년 전 1

가로와 세로가 혼재되어 사용되고 있습니다. 반례를 참고하시는 게 좋을 것 같습니다.

그리고 출력하실 때 엔터랑 같이 하셔야 합니다.

Input:
2
3 2 1
2 1
2 3 1
1 2

Output:
1
1

ghdtmdwo123 5년 전 0

감사합니다!

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

문제

문제

출처

ICPC

반례를 못찾겠어용;

ghdtmdwo123 5년 전 0

evenharder 5년 전 1

ghdtmdwo123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말