BFS 검색 Problem 1009 연속 보기
간단 한 제목: 한 바둑판 에 몇 개의 바둑 알 을 놓 았 는데 만약 에 두 개의 같은 (위치 가 다른) 바둑 알 이 한 줄 로 연결 되 고 전환 횟수 가 두 번 을 초과 하지 않 으 면 이 를 없 앨 수 있다.바둑판 과 바둑 알, 그리고 없 애 려 는 두 개의 바둑 알 의 위 치 를 제시 하 다.제거 할 수 있다 면 "YES" 를 출력 하고, 그렇지 않 으 면 "NO" 를 출력 합 니 다.
문제 풀이 사고의 형성 과정: BFS 를 이용 하여 검색 을 하고 요구 에 부합 되 는 다음 단 계 는 모두 3 가지 요구 가 있다.
①: 연결선 은 반드시 바둑판 안에 있어 야 하 며 밖에서 돌아 나 갈 수 없다.
②: 다음 목표 구역 은 그 어떠한 방향 으로 도 지나 가지 않 거나 새로운 방법 으로 전환 하 는 횟수 가 적다.
③: 이 구역 에 알 이 없습니다 (목 표를 찾 으 면 바로 return 으로 돌아 갑 니 다).
메모: 선택 한 두 개의 바둑 알 의 유형 이 다 르 거나 그 중 임의의 위치 에 바둑 알 이 없 으 면 'NO' 를 직접 출력 해 야 합 니 다.
소감: 어렵 지 않 은 문제 하나 에 WA 가 16 번.............................................................. 마지막 으로 WA 를 발견 한 이 유 는 이 출력 "NO" 라면 주 함수 의 조건 을 0 이 아 닌 대응 하 는 - 1 로 써 야 하기 때 문 입 니 다. 반복 검 사 를 했 지만 발견 되 지 않 았 다 니..
그리고 중간 에 생각 하지 못 한 게 있 는데...
처음에 사용 한 DFS 는 시간 을 초과 한 후에 다시 BFS 로 바 뀌 었 다.하지만 가지치기 처리 가 잘 되면 DFS 도 가능 할 것 같다.
처음 보고 3 차원 수 조 를 배 웠 으 니 쓰기 좋다.
코드 효율 을 높이 기 위해 조건 의 통합 에 주의 하 세 요.
어쨌든... 드디어 AC...
코드:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define INF 10000
int cmap[1001][1001];
int mark[1001][1001][4];
int query[4];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,m;
int BFS()
{
queue<int>s;
s.push(query[0]); // 4 , (r), (c), (state), (cnt)。
s.push(query[1]);
s.push(-1);
s.push(-1);
while(!s.empty())
{
int r=s.front();
s.pop();
int c=s.front();
s.pop();
int state=s.front();
s.pop();
int cnt=s.front();
s.pop();
for(int i=0;i<4;++i){ //i 。i=0,1,2,3 , , , 。
int t_cnt=cnt;
if(i!=state)
++t_cnt;
if(t_cnt>2)
continue;
if(r+dir[i][0]==query[2]&&c+dir[i][1]==query[3])
return 1;
if(r+dir[i][0]>=0&&r+dir[i][0]<n&&c+dir[i][1]>=0&&c+dir[i][1]<m)
if(mark[r+dir[i][0]][c+dir[i][1]][i]>t_cnt) //
if(cmap[r+dir[i][0]][c+dir[i][1]]==0){
// cout<<r<<' '<<c<<' '<<"go"<<endl;
s.push(r+dir[i][0]);
s.push(c+dir[i][1]);
s.push(i);
s.push(t_cnt);
mark[r+dir[i][0]][c+dir[i][1]][i]=t_cnt;
}
}
}
return -1;
}
int main()
{
freopen("1.txt","r",stdin);
while(1)
{
scanf("%d%d",&n,&m);
if(n==0)
return 0;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
cin>>cmap[i][j];
int q;
scanf("%d",&q);
for(int i=0;i<q;++i){
scanf("%d%d%d%d",&query[0],&query[1],&query[2],&query[3]);
--query[0];
--query[1];
--query[2];
--query[3];
memset(mark,INF,sizeof(mark));//INF
if(cmap[query[0]][query[1]]!=cmap[query[2]][query[3]]||cmap[query[0]][query[1]]==0||cmap[query[2]][query[3]]==0||(query[0]==query[2]&&query[1]==query[3]))
printf("NO
");
else if(BFS()==1)
printf("YES
");
else if(BFS()==-1)
printf("NO
");
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.