글 읽기 - 테스트 케이스 질문드립니다.

leechhe 8년 전 0

코드는 BFS로 탐색하다가 visited[x][y] 가 true인 곳을 발견하면 사이클이 생겼다는 의미이므로 -1를 리턴하도록 하였습니다.

다른 분들이 올리신 질문-답변을 봤는데 그래도 맞는 것 같은데...

부탁드리겠습니다 :)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int, int> intPair;
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
char board[51][51];
bool visited[50][50] = { false };
int main(){
    int n,m; scanf("%d%d",&n,&m);
    int ret = 0;
    for( int i = 0 ; i < n ; ++i ){
        scanf("%s", board[i]);
    }
    queue<intPair> q;
    visited[0][0] = true;
    q.push(make_pair(0, 0));
    while (!q.empty()) {
        int len = (int)q.size();
        for( int i = 0 ; i < len ; ++i ){
            int x = q.front().first, y = q.front().second;
            q.pop();
            for( int k = 0 ; k < 4 ; ++k ){
                int cx = x+dx[k]*(board[x][y]-'0'), cy = y+dy[k]*(board[x][y]-'0');
                if (0<= cx && cx < n && 0 <= cy && cy < m) {
                    if (board[cx][cy] == 'H') continue;
                    if( visited[cx][cy] ){
//                        printf("re-visit from %d,%d to %d,%d on turn %d\n",x,y,cx,cy,ret);
                        ret = -1;
                        break;
                    }
                    visited[cx][cy] = true;
                    q.push(make_pair(cx, cy));
                }
            }
            if( ret < 0 ) break;
        }
        if( ret < 0 ) break;
        ++ret;
    }
    printf("%d",ret);
    return 0;
}

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

문제

문제

출처

ICPC

테스트 케이스 질문드립니다.

leechhe 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말