dfs 미궁 탈출 문제 해결

미궁 을 벗어나다
제목 설명
작은 지 는 나 쁜 놈 에 게 A x A 칸 으로 구 성 된 매트릭스 미로 에 잡 혔 다.* 로 소지 가 지나 갈 수 있 는 칸 을 표시 합 니 다.'#' 는 소지 가 지나 갈 수 없 는 칸 을 나타 낸다.소지 의 시작 위 치 는 왼쪽 상단 에 있 고 그 는 오른쪽 아래 칸 에 도착 해 야 미 로 를 벗 어 날 수 있다.샤 오 지 는 한 걸음 한 걸음 상하 좌우 네 방향 으로 인접 한 칸 으로 이동 할 수 있 는데 전 제 는 목표 형식 에 장애 가 없어 야 한 다 는 것 이다.
이제 소 지 는 마법 으로 칸 의 장 애 를 제거 할 수 있다. 즉, \ # 가 * 가 되 어 지나 갈 수 있 게 한다.최대 B 곳 의 장 애 를 제거 할 수 있 는 상황 에서 샤 오 지 는 최소한 몇 걸음 을 움 직 이면 미 로 를 벗 어 날 수 있 는 지 계산 해 보 세 요.
첫 줄 에 두 개의 정수 A 와 B 를 포함 하 는 것 을 입력 하 십시오.아래 A 줄 은 A x A 의 행렬 을 포함한다.행렬 은 왼쪽 상단 과 오른쪽 하단 을 * 로 보장 합 니 다.정 수 를 출력 하여 답 을 표시 하 다.소지 가 미로 에서 벗 어 나 지 못 하면 출력 - 1.
샘플 입력 52 * \ # * \ # * \ # * * \ # * * \ # # \ # # \ # * \ # * * * * * * * * 샘플 출력 8
문제 풀이 의 사고 방향.
dfs 로 해결 할 수 있 는 미로 문제 가 분명 합 니 다.그러나 이 요 구 는 최소 몇 걸음 을 이동 해 야 하기 때문에 우 리 는 매번 찾 는 경로 의 걸음 수 를 기록 하고 그 중에서 가장 작은 것 을 찾 아야 한다.
우 리 는 이 문제 가 칸 의 장 애 를 제거 할 수 있다 는 것 을 알 게 되 었 다. 즉, \ # 가 * 로 변 하지만 가장 많은 b 곳 을 제거 할 수 있다.그래서 우 리 는 하나의 변수 로 지금까지 모두 몇 개 를 없 앴 는 지 기록 할 수 있다. 이 숫자 가 b 보다 작 으 면 우 리 는 계속 갈 수 있다.
재 귀 중지 조건 은 바로 오른쪽 아래 까지 가 는 것 이 고 이때 제거 하 는 장애 의 개 수 는 b 보다 적다.재 귀 과정 은 우리 가 네 방향 으로 한 걸음 더 가 려 고 하 는 것 이다. 만약 에 이 걸음 으로 도착 하 는 곳 이 미로 범위 안에 있다 면.그리고 지나 가지 않 았 습 니 다. 그리고 이때 장 애 를 없 애 는 개 수 는 b 보다 적 습 니 다. 그러면 우 리 는 이 걸음 을 걸 어서 계속 내 려 갈 수 있 습 니 다.주의해 서 걸 을 때 우 리 는 이 점 이 장애 인지 통로 인지 판단 할 필요 가 없다. 우 리 는 현재 장 애 를 없 애 는 개수 만 판단 하면 된다.
코드 는 다음 과 같다.

#include
using namespace std;
char s[1000][1000];
bool vis[1000][1000];//      
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};//      
int a,b;
int ans = 1e9;//         
int v = 0;//          ，         -1
//        ，     x,y,        ，              。
void dfs(int x,int y,int cnt,int num){
	if(x == a-1 && y == a-1 && num<=b){
		ans = min(ans,cnt);
		v++;
		return;
	}
	//printf("1111
");
	for(int i = 0; i<4; i++){
		int p = x+dir[i][0];
		int q = y+dir[i][1];
		if(p >= 0 && p < a && q >= 0 && q < a && vis[p][q] == false && num<=b){
			vis[p][q] = true;//       
			cnt++;//     1
			if(s[p][q] == '#') num++;//         ，              1
			dfs(p,q,cnt,num);
			vis[p][q] = false;
			cnt--;
			if(s[p][q] == '#') num--;
		}
	}
	return;
}
int main(){
	scanf("%d%d",&a,&b);
	for(int i = 0; i< a; i++){
		scanf("%s",s[i]);
	}
	memset(vis,false,sizeof(vis));
	vis[0][0] = true;
	dfs(0,0,0,0);
	if(v == 0) printf("-1");
	else printf("%d",ans);
	return 0;
}