글 읽기 - 반례를 모르겠습니다

nosouls2 3년 전 0

테스트 케이스는 전부 맞았습니다. 반례를 도저히 모르겠습니다.

#include <iostream>
#include <vector>
using namespace std;

char board[22][22];
char order[2][20];

char ans[21];
int H,W,N,flag=0;

typedef struct{
	int y,x;
}Dir;

Dir d[4]={ {-1, 0}, {1, 0}, {0, 1}, {0, -1} };

int next(char dir) {
	if(dir=='W') return 0;
	if(dir=='S') return 1;
	if(dir=='D') return 2;
	if(dir=='A') return 3;
}

void dfs(vector<char> &memo,int nx,int ny,int idx,int I) {
	if(board[ny][nx]=='@') return;	
	if(idx==N) return;
	memo[idx]=order[I][idx];
	nx+=d[next(order[I][idx])].x;
	ny+=d[next(order[I][idx])].y;
	if(board[ny][nx]=='Z') {
		flag=1;
		for(int i=0;i<=idx;i++){
			ans[i]=memo[i];
		}
		return;
	}
	
	/*printf("idx : %d\n",idx);
	printf("path : ");
	for(int i=0;i<=idx;i++){
		printf("%c",memo[i]);
	}
	puts("");
	for(int i=0;i<=H+1;i++){
		for(int j=0;j<=W+1;j++){
			if(ny==i&&nx==j) printf("C");
			else printf("%c", board[i][j]);
		}
		puts("");
	}
	puts("");*/
	
	dfs(memo,nx,ny,idx+1,0);
	dfs(memo,nx,ny,idx+1,1);
}

void solve(vector<char> &memo,int dx,int dy){
	dfs(memo,dx,dy,0,0);
	dfs(memo,dx,dy,0,1);
}

int main(){
	int dx,dy;
	cin >> H >> W;
	for(int i=0;i<=H+1;i++){
		for(int j=0;j<=W+1;j++){
			if(i==0||j==0||i==H+1||j==W+1) board[i][j] = '@';
			else cin >> board[i][j];
			if(board[i][j]=='D') dy=i,dx=j;
		}
	}
	cin >> N;
	vector<char> memo(N);
	for(int i=0;i<N;i++){
		cin >> order[0][i] >> order[1][i];
	}
	for(int i=0;i<21;i++){
		ans[i]='0';
	}
	/*
	for(int i=0;i<=H+1;i++){
		for(int j=0;j<=W+1;j++){
			cout << board[i][j];
		}
		cout << endl;
	}
	for(int i=0;i<N;i++){
		cout << order[0][i] << order[1][i] << endl;
	}
	*/
	solve(memo, dx, dy);
	if(!flag) puts("NO");
	else {
		puts("YES");
		for(int i=0;ans[i]!='0';i++){
			printf("%c",ans[i]);
		}
	}
}

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

문제

문제

출처

ICPC

반례를 모르겠습니다

nosouls2 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말