글 읽기 - 제출하자마자 틀립니다 반례나 틀린부분있을까요 ㅜ?

isvara 4년 전 0

출력양식은 맞췄고 게시판에 다른 예시는 다 잘 돌아가는데 어디가 틀린걸가요?

반례나 잘못된 코드 부분이 있다면 지적해주시면 감사하겠습니다.

#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<string.h>
using namespace std;

#define debug cout

const int dx[4] = { 0,0,1,-1 };
const int dy[4] = { 1,-1,0,0 };
const int INF = 1e9;

int N, M,tot;
int ans;
char b[32][32];
bool chk[32][32];
bool determine(int y, int x) {
	return y >= 0 && x >= 0 && y < N && x < M && b[y][x] != '*' && !chk[y][x];
}
void simulate(int y, int x, int cnt,int step)
{
	if (cnt == tot)
	{
		ans = min(ans, step);
		return;
	}
	for (int k = 0; k < 4; k++) {
		int cur = 0;
		int cx = x;
		int cy = y;

		while (true) {
			cx += dx[k];
			cy += dy[k];
			if (!determine(cy, cx)) {
				cx -= dx[k];
				cy -= dy[k];
				break;
			}
			cur++;
			chk[cy][cx] = true;
		}
		if (cy == y && cx == x) //같은 방향 pass
			continue;
		simulate(cy, cx, cnt+cur,step+1);

		//back.
		while (cx != x || cy != y) {
			chk[cy][cx] = false;
			cx -= dx[k];
			cy -= dy[k];
		}
		
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
	while (!cin.eof()) {
		memset(chk, false, sizeof(chk));
		ans = INF;
		tot = 0;
		cin >> N >> M;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				cin >> b[i][j], tot += (b[i][j] == '.');

		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (b[i][j] == '.'){
					chk[i][j] = true;
					simulate(i, j, 1, 0);
					chk[i][j] = false;
				}
		if(ans==INF) cout <<"Case "<<t<<": "<< -1<<"\n";
		else cout << "Case " << t << ": " << ans << "\n";
		t++;
	}
}

skyp0714 2년 전 0

저랑 방식이 똑같으신데.. 저도 50%에서 바로 틀렸다고 떠서요ㅜ

혹시 해결하셨나요??

isvara 2년 전 0

아직해결못했습니다 ㅜ.

skyp0714 2년 전 0

한번에 쭉 이동하지말고 한칸씩 이동하면 맞다고 나오던데

전자의 방식에서 반례를 못찾겠어요ㅜㅜ

skyp0714 2년 전 0

저는 chk 배열 없애고 b 배열만 써서 해결했습니다.

처음에 .을 지나면서 #으로 바꾸고

다시 백하면서 #를 .으로 바꾸는 식으로 했더니 통과했습니다.

근데 chk 배열로 했을 때 뭐가 문젠지는 잘 모르겠습니다ㅜ

제 소스 추가할게요

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
char map[31][31];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}, n, m;
int go(int x, int y);
bool isinside(int x, int y){
    return x>=0 && x<n && y>=0 && y<m;
}
int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 0;
    while(cin >> n >> m){
        t++;
        int min = 1000001;
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                cin >> map[i][j];
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map[i][j] == '.'){
                    map[i][j] = '#';
                    int tmp = go(i, j);
                    map[i][j] = '.';
                    if(min > tmp) min = tmp;
                }
            }
        }
        if(min == 1000001) min = -1;
        cout << "Case " << t << ": " << min << '\n';
    }
    return 0;
}
int go(int x, int y){
    int i, min = 1000001;
    int cnt;
    for(i=0; i<4; i++){
        
        int nx = x + dx[i], ny = y + dy[i];
        cnt = 0;
        
        while(isinside(nx, ny)){
            if(map[nx][ny] == '.'){
                cnt++;
                map[nx][ny] = '#';
                nx += dx[i]; ny += dy[i];
            }else{
                break;
            }
        }
        
        if(cnt){
            nx = nx - dx[i]; ny = ny - dy[i];
            int tmp = go(nx, ny);
            if(min > tmp) min = tmp;
            while(cnt--){
                map[nx][ny] = '.';
                nx -= dx[i]; ny -= dy[i];
            }
        }
        
    }
    if(min == 1000001){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map[i][j] == '.'){
                    return min;
                }
            }
        }
        return 0;
    }
    return min+1;
}

skyp0714 2년 전 0

혹시나 연산자 우선순위 문젠가 싶어서

&& !chk[][] -> && chk[][] == false 로 바꿨더니 통과했습니다....

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

문제

문제

출처

ICPC

제출하자마자 틀립니다 반례나 틀린부분있을까요 ㅜ?

isvara 4년 전 0

skyp0714 2년 전 0

isvara 2년 전 0

skyp0714 2년 전 0

skyp0714 2년 전 0

skyp0714 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말