5978 Problem F [귀속 입문] 미로를 걷다
17986 단어 경험 총결
제목은 n*m칸의 미로(n줄, m열이 있음을 나타냄)가 있는데 그 중에서 갈 수 있는 것도 있고 갈 수 없는 것도 있다. 만약에 1로 갈 수 있다는 것을 표시하면 0은 갈 수 없다는 것을 나타낸다. 파일은 이 n*m개의 데이터와 시작점, 끝점을 읽는다(시작점과 끝점은 모두 두 개의 데이터로 묘사하고 각각 이 점의 줄 번호와 열 번호를 나타낸다).지금 네가 프로그래밍을 해서 모든 실행 가능한 길을 찾아내야 한다. 걷는 길에 중복된 점이 없으면 위아래 좌우 네 방향만 갈 수 있다.만약 한 개의 길이 모두 실행할 수 없다면, 상응하는 정보를 출력한다.왼쪽 위와 오른쪽 아래 순서로 넓혀주세요. 즉, (0,-1), (-1,0), (0,1), (1,0).
첫 번째 줄은 n, m(1
샘플 입력 5 6 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 6
샘플 출력(1,1) -> (2,1) -> (2,2) -> (2,3) -> (2,4) -> (2,5) -> (3,5) -> (3,4) -> (3,3) -> (4,3) -> (4,4) -> (5,5) -> (5,6) (1,1) -> (2,3) -> (2,4) -> (2,4) -> (3,5) -> (3,5) -> 3,4) ->(4,4) ->(4,5) ->(5,5) ->(5,6)(1,1) ->(2,2) ->(2,3) ->(2,4) ->(2,5) ->(3,5) ->(5,5) ->(5,6)(1,1) ->(2,2) ->(2,4) ->(3,4) ->(3,3) -> (4,3) ->(4,4) ->(4,5) ->(5,5) ->(5,6)(1,1) ->(2,1) ->(2,2) ->(2,3) ->(2,4) ->(3,4) ->(3,5) ->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
제시 [알고리즘 분석] 하나의 a수조로 미궁이 갈 수 있는 상황을 저장하고 또 하나의 수조 b로 어떤 점을 저장하고 지나갔는지 알려준다.각 점은 두 개의 숫자로 설명하는데, 하나는 줄 번호를 표시하고, 다른 하나는 열 번호를 표시한다.어떤 점(x, y)에 대해 네 개의 갈 수 있는 방향의 점은 다음과 같다.
1 x,y 3
4 대응하는 위치는 (x, y-1), (x-1, y), (x, y+1), (x+1, y)이다.따라서 각 점은 네 가지 방향을 탐색해야 한다. 만약에 (수조 b에 상응하는 점의 값은 0) 지나가지 않고 (수조 a에 상응하는 점의 값은 1)동시에 경계를 넘지 않고 걸어가서 종점에 도착했는지 확인하고 종점에 도착하면 출력하는 길을 가야 한다. 그렇지 않으면 계속 걸어야 한다.
이 검색 프로세스는 다음과 같이 설명합니다.
procedure search(x, y, b, p);{x, y는 어떤 점, b는 이미 지나간 점의 상황, p는 이미 지나간 길입니다}
begin for i:=1 to 4 do {각각 4개의 점을 탐색합니다}begin은 현재 점의 위치, 이미 지나간 상황과 지나간 길을 기억합니다.만약 i점(xl, y1)이 갈 수 있다면 걸어가세요.
종점에 도달한 경우 경로와 함께 갈 수 있는 정보가 출력됩니다.
그렇지 않으면 계속해서 새로운 점에서 검색(xl, y1, b1, p1)을 찾습니다. end; end; 어떤 상황은 명백히 무해하다. 예를 들어 기점에서 종점까지의 직사각형 중 한 줄이나 한 열이 모두 0이고 도로가 통하지 않는 것이 분명하다. 이런 상황에 대해 여분의 가지를 빨리 잘라서 결론을 얻어야 한다. 이것이 바로 검색에서 말한 가지치기이다.시작점부터 아래로 층층이 이어지는 결점은 나뭇가지처럼 보이지만 그중의'마른 가지'인 뚜렷하게 쓸모없는 노드에 대해서는 먼저 잘라서 검색 속도를 높일 수 있다.
경험 총결에 이 문제는 구덩이가 있다!!위에 굵게 붙인 그 한마디는 사람을 괴롭히는 것이다. 이 문제는 제시에서 이른바 가지치기를 필요로 하지 않는다. 만약 정말 이렇게 가지치기를 한다면 맞출 수 없다. 원인은 다음과 같다. 입력 데이터: 44010 010 1 1 1 2 3 4 기점(1, 2)에서 종점(3, 4)까지의 직사각형은 다음과 같다.아니오, (1,2)->(2,2)->(3,2)->(4,2)->(4,3)->(4,4)->(3,4)가 유일한 해입니다.그러므로 제시된 가지치기를 하지 마십시오. 이외에 무해 출력-1의 특판에 주의하십시오. 다른 문제는 크지 않습니다.ω`ฅ)emmmm는 앞의 몇 가지 절차의 경험을 통해 비귀속을 쓰는 것이 그렇게 골치 아픈 것은 아니다!좋아!!비귀속 승진의 방법은 스스로 쓰는 것이다. 절대 다른 사람의 코드를 보지 말고 조금씩 정리해야 점차적으로 발전할 수 있다.
귀속 코드
#include
",answer[i][0],answer[i][1]);
}
count++;
return ;
}
for(int i=0;i<4;i++)
{
int new_x=x+direct[i][0];
int new_y=y+direct[i][1];
if(judge(new_x,new_y))
{
flag[new_x][new_y]=true;
answer[index][0]=new_x;
answer[index][1]=new_y;
dispose(new_x,new_y,index+1);
flag[new_x][new_y]=false;
}
}
}
int main()
{
while(~scanf("%d %d",&m,&n))
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&atlas[i][j]);
flag[i][j]=false;
}
}
scanf("%d %d",&start_x,&start_y);
scanf("%d %d",&last_x,&last_y);
index=0;
count=0;
if(judge(start_x,start_y))
{
flag[start_x][start_y]=true;
answer[index][0]=start_x;
answer[index][1]=start_y;
dispose(start_x,start_y,index+1);
if(count==0)
{
printf("-1
");
}
}
else
{
printf("-1
");
}
}
return 0;
}비귀속 코드
#include
",answer[i][0],answer[i][1]);
}
else
{
printf("(%d,%d)->",answer[i][0],answer[i][1]);
}
}
count++;
pflag=true;
}
if(pflag==true)
{
flag[top->x][top->y]=false;
for(int i=0;i<4;i++)
tflag[top->x][top->y][i]=false;
process.pop();
pflag=false;
continue;
}
int f=0;
for(int i=0;i<4;i++)
{
int new_x=top->x+direct[i][0];
int new_y=top->y+direct[i][1];
if(judge(new_x,new_y)&&tflag[top->x][top->y][i]==false)
{
tflag[top->x][top->y][i]=true;
node *temp=new node();
temp->number=top->number+1;
temp->x=new_x;
temp->y=new_y;
temp->type=i;
flag[new_x][new_y]=true;
answer[temp->number][0]=new_x;
answer[temp->number][1]=new_y;
process.push(temp);
f=1;
break;
}
}
if(f==0)
{
pflag=true;
}
}
}
int main()
{
while(~scanf("%d %d",&m,&n))
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&atlas[i][j]);
flag[i][j]=false;
for(int k=0;k<4;k++)
tflag[i][j][k]=false;
}
}
scanf("%d %d",&start_x,&start_y);
scanf("%d %d",&last_x,&last_y);
count=0;
if(judge(start_x,start_y))
{
dispose();
if(count==0)
{
printf("-1
");
}
}
else
{
printf("-1
");
}
}
return 0;
}좋은 웹페이지 즐겨찾기
