글 읽기 - 87퍼 즈음에서 틀렸다고 하네요 ㅠㅠ 어떤 반례가 있을까요?

shwjdgh3842 2년 전 1

87퍼 즈음에서 틀렸다고 하네요 ㅠㅠ 어떤 반례가 있을까요?

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
using namespace std;
int r, c;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
char arr[20][20];
bool ar[20][20];
vector<char> v;
int max_path = 0;
//단순 dfs로는 안되니까 path를 변수로 추가해서 해결해보자
void dfs(int x, int y, int path) {
	if (max_path < path) {
		max_path = path;
	}
	bool d = false;
	//말이 지나간 알파벳과 같은것이 등장
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == arr[x][y]) {
			d = true;
			break;
		}
	}
	if (x < 0 || y < 0 || x >= r || y >= c || ar[x][y] == true) {
		return;
	}
	else if (d) {
		return;
	}
	else {
		ar[x][y] = true;
		v.push_back(arr[x][y]);				
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
            //시간초과 안걸리도록..
			if (nx >= 0 && ny >= 0 && nx < r && ny < c && ar[nx][ny] == false) {
				dfs(nx, ny, path + 1);
			}
		}		
		v.pop_back();
		ar[x][y] = false;
	}
	return;
}


int main() {	
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> arr[i][j];
		}
	}
	dfs(0, 0, 0);
	cout << max_path;
	
}

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

문제

문제

출처

ICPC

87퍼 즈음에서 틀렸다고 하네요 ㅠㅠ 어떤 반례가 있을까요?

shwjdgh3842 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말