글 읽기 - 어디서 틀렸는지 모르겠습니다

skyp0714 2년 전 0

게시판에 예시는 다 맞았습니다.

공을 이동할때 한번에 장애물을 만나기 전까지 쭉 이동시키는 방법으로 했을 때 틀렸는데

한칸씩 이동시키면 맞았습니다.

전자의 방법으로 했을 때의 반례가 뭔지 모르겠어서 부탁드립니다ㅜ

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
char map[31][31];
bool chk[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] == '.'){
                    memset(chk, false, sizeof(chk));
                    int tmp = go(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){
    chk[x][y] = true;
    
    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] == '.' && chk[nx][ny] == false){
                cnt++;
                chk[nx][ny] = true;
                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--){
                chk[nx][ny] = false;
                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] == '.' && !chk[i][j]){
                    return min;
                }
            }
        }
        return 0;
    }
    return min+1;
}

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

문제

문제

출처

ICPC

어디서 틀렸는지 모르겠습니다

skyp0714 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말