dfs를 이용한 완탐시, 방문 해제 모두 하고 return true

9944번: NxM 보드 완주하기

틀린 코드(42번째 줄에서 바로 return true 하면 안됨)

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
#define all(v) v.begin(), v.end()
#define MAX 31
#define INF 1000
#define AVAIL '.'
#define WALL '*'
 
using namespace std;
typedef pair<int, int> pi;
 
int N, M;
int ANS, FULL;
char d[MAX][MAX];
int dr[]{0, 1, 0, -1};
int dc[]{1, 0, -1, 0};
 
bool avail(int r, int c)
{
    if(r < 0 || r >= N || c < 0 || c >= M || d[r][c] == WALL) return false;
    else return true;
}
 
bool dfs(int cr, int cc, int dep, int acc)
{
    if(acc+1 == FULL){
        ANS  = min(ANS,  dep);
        return true;
    }
 
    for(int i = 0; i < 4; i++){
        if(!avail(cr+dr[i], cc+dc[i])) continue;
        
        int nr = cr;
        int nc = cc;
        while(avail(nr+dr[i], nc+dc[i])){
            d[nr][nc] = WALL;
            acc += 1;
            nr += dr[i];
            nc += dc[i];
        }
        if(dfs(nr, nc, dep+1, acc)) return true;
        
        while(cr != nr || cc != nc){
            nr -= dr[i];
            nc -= dc[i];
            d[nr][nc] = AVAIL;
            acc -= 1;
        }
    }
 
    return false;
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
 
    int T = 1;
    while(cin >> N >> M){
        int cur_full = 0;
        for(int r = 0; r < N; r++){
            string tmp; cin >> tmp;
            for(int c = 0; c < M; c++){
                d[r][c] = tmp[c];
                if(d[r][c] == AVAIL) cur_full += 1;
            }
        }
        ANS  = INF;
        FULL = cur_full;
 
        for(int r = 0; r < N; r++){
            for(int c = 0; c < M; c++){
                if(d[r][c] == WALL) continue;
                
                dfs(r, c, 0, 0);
            }
        }
 
        cout << "Case " << T << ": " << ((ANS  == INF)? -1: ANS)  << endl;
        T += 1;
    }
    
 
    return 0;
}cs

반례 출처 : https://www.acmicpc.net/board/view/35161

10 10
.........*
......*..*
..***.*..*
..***....*
..****...*
..****...*
..****...*
..****...*
.........*
.........*

// Case 1: 11

맞은 코드

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
#define all(v) v.begin(), v.end()
#define MAX 31
#define INF 1000
#define AVAIL '.'
#define WALL '*'
 
using namespace std;
typedef pair<int, int> pi;
 
int N, M;
int ANS, FULL;
char d[MAX][MAX];
int dr[]{0, 1, 0, -1};
int dc[]{1, 0, -1, 0};
 
bool avail(int r, int c)
{
    if(r < 0 || r >= N || c < 0 || c >= M || d[r][c] == WALL) return false;
    else return true;
}
 
bool dfs(int cr, int cc, int dep, int acc)
{
    if(acc+1 == FULL){
        ANS  = min(ANS,  dep);
        return true;
    }
 
    for(int i = 0; i < 4; i++){
        if(!avail(cr+dr[i], cc+dc[i])) continue;
        
        bool flag = false;
        int nr = cr;
        int nc = cc;
        while(avail(nr+dr[i], nc+dc[i])){
            d[nr][nc] = WALL;
            acc += 1;
            nr += dr[i];
            nc += dc[i];
        }
        if(dfs(nr, nc, dep+1, acc)) flag = true;
        
        while(cr != nr || cc != nc){
            nr -= dr[i];
            nc -= dc[i];
            d[nr][nc] = AVAIL;
            acc -= 1;
        }
 
        if(flag) return true;
    }
 
    return false;
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
 
    int T = 1;
    while(cin >> N >> M){
        int cur_full = 0;
        for(int r = 0; r < N; r++){
            string tmp; cin >> tmp;
            for(int c = 0; c < M; c++){
                d[r][c] = tmp[c];
                if(d[r][c] == AVAIL) cur_full += 1;
            }
        }
        ANS  = INF;
        FULL = cur_full;
 
        for(int r = 0; r < N; r++){
            for(int c = 0; c < M; c++){
                if(d[r][c] == WALL) continue;
 
                dfs(r, c, 0, 0);
            }
        }
 
        cout << "Case " << T << ": " << ((ANS  == INF)? -1: ANS)  << endl;
        T += 1;
    }
    
 
    return 0;
}cs