글 읽기 - 1857 접근법 질문입니다.

nisroeld99 7년 전 0

맞게 접근한 것같은데 답이 안나오네요

푸는법

1. bfs한번돌려서 최소방석 개수 구하기

2. bfs다시돌려서 최소방석개수 만족하는 경로 수 구하기

이렇게했는데, 0%에서 바로 틀렸다고 뜨네요 ..

틀릴만한거

1. unsinged long long 범위 체크

2. -1 출력

3... queue 다시 돌릴떄, visit , d 초기화하기

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii ;
typedef pair<ii,int> iii ;
int n,m;
bool visit[50][50];
ull d[50][50];
bool inRange (int y,int x){
    if ( y<1 || x < 1 || y> n || x> m|| visit[y][x] ) return false;
    return true;
}

int g[50][50];



int dy[8]={-2,-2,-1,1,2,2,-1,1}, dx[8]={-1,1,-2,-2,-1,1,2,2};
int main(){
    
    int sy,sx;
  freopen("input.txt","r", stdin);
    queue<ii> q;
    scanf("%d%d",&n,&m);
    for (int i =1; i<=n; i++){
        for (int j=1 ;j<=m; j++) {
            scanf("%d",&g[i][j]);
            if (g[i][j] == 3){ //시작지점 큐에 넣기
                sy= i ; sx= j;
                q.push(ii(i,j));
                visit[i][j] = true;
            }
        }
    }
    
    ull ans = 184467440737095516 ;
    ull temp = 0;
    bool check = false;
    
    while (!q.empty()){ // 최소 방석의 수 구하는 q
        ii temp = q.front();q.pop();
        int now_y = temp.first;
        int now_x = temp.second;
    
        for (int i = 0 ; i<8 ; i++){
            int ny = now_y + dy[i];
            int nx = now_x + dx[i];
            
            if (!inRange(ny,nx))continue;  //범위 체크와 방문 체크
            if ( g[ny][nx] == 2) continue ; //돌부리면
            else if ( g[ny][nx] ==1 ){ //방식이 이미 깔려있으면,
                check= true;
                q.push(ii(ny,nx));
                d[ny][nx] = d[now_y][now_x] ;
                visit[ny][nx] =true;
            }
            else if ( g[ny][nx] ==4){//도착지면
                if ( d[now_y][now_x] < ans ){ // 최소 방석 경로 찾을때까지 큐 계속 돌리기
                    check= true;
                    ans = d[now_y][now_x];
                }
                continue;
            }
            else {//
                q.push(ii(ny,nx));
                d[ny][nx] = d[now_y][now_x]+1;
                visit[ny][nx] = true;
            }
            
        }
    }
    
    if ( !check){
        printf("-1\n");
        return 0;
    }else {
        printf("%lld\n",ans);
    }
    
    memset(visit,false, sizeof(visit));
    memset(d,0,sizeof(d));
    while (!q.empty()){
        q.pop();
    }
    q.push(ii(sy,sx));
    visit[sy][sx] = true;
    
    //최소방석 수를 가지는 경로의 개수 구하기
    
    ull cnt = 0 ;
    while (!q.empty()){
        ii temp = q.front();q.pop();
        int now_y = temp.first;
        int now_x = temp.second;
        
        for (int i = 0 ; i<8 ; i++){
            int ny = now_y + dy[i];
            int nx = now_x + dx[i];
            
            if (!inRange(ny,nx))continue;  //범위 체크와 방문 체크
            if ( g[ny][nx] == 2) continue ; //돌부리면
            else if ( g[ny][nx] ==1 ){ //방식이 이미 깔려있으면,
                q.push(ii(ny,nx));
                d[ny][nx] = d[now_y][now_x] ;
                visit[ny][nx] =true;
            }
            else if ( g[ny][nx] ==4  ){//도착지면
                if (d[now_y][now_x] > ans) continue;
                cnt++;
                continue;
            }
            else {//
                if ( d[now_y][now_x]+1 > ans) continue;
                q.push(ii(ny,nx));
                d[ny][nx] = d[now_y][now_x]+1;
                visit[ny][nx] = true;
            }
            
        }
    }
    printf("%lld\n",cnt);

}

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

문제

문제

출처

ICPC

1857 접근법 질문입니다.

nisroeld99 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말