hdu 2102 A 계획 bfs 검색 문제 풀이 보고서
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 15439 Accepted Submission(s): 3851
Problem Description
불쌍 한 공 주 는 마왕 에 게 한 번 씩 납 치 돼 기사 들 에 게 구 조 된 후 불행 하 게 도 그녀 는 다시 생명의 시련 에 직면 하 게 되 었 습 니 다.마왕 은 T 시 에 공 주 를 잡 아 먹 을 것 이 라 고 메 시 지 를 보 냈 습 니 다. 공주 의 고 기 를 먹 어도 오래 살 수 있다 는 소문 을 믿 었 기 때 문 입 니 다.늙 은 왕 은 마음 이 급 하여 천하 의 용 사 를 불 러 공 주 를 구 하 겠 다 고 고 했 습 니 다.하지만 공 주 는 익숙 해 졌 습 니 다. 지 용의 기사 LJ 가 구 해 낼 수 있 을 거 라 고 믿 었 습 니 다.
현재 밀정 에 따 르 면 공 주 는 2 층 미궁 에 갇 혀 있다. 미궁 의 입 구 는 S (0, 0, 0) 이 고 공주 의 위 치 는 P 로 표시 하 며 시공 전송 기 는\# 로 표시 하고 벽 은 * 로 표시 하 며 평지 용 으로 표시 한다.기사 들 은 시공 전송 기 에 들 어가 면 다른 층 의 상대 적 인 위치 로 옮 겨 지지 만, 옮 겨 진 위치 가 벽 이 라면 기사 들 은 부 딪 혀 죽는다.기사 들 은 1 층 에서 한 칸 씩 이동 하 는 데 1 시간 이 걸린다.층 간 의 이동 은 시공 전송 기 를 통과 할 수 있 을 뿐 어떠한 시간 도 필요 없다.
Input
입력 한 첫 줄 C 는 모두 C 개의 테스트 데 이 터 를 표시 하고 테스트 데이터 의 앞 줄 마다 세 개의 정수 N, M, T 가 있다.N, M 미궁 의 크기 N * M (1 < = N, M < = 10). T 는 위 와 같다. 이 어 진 전 N * M 은 미궁 의 1 층 배치 상황 을 나타 내 고, 후 N * M 은 미궁 2 층 배치 상황 을 나타 낸다.
Output
기사 들 이 T 시간 에 공 주 를 찾 을 수 있다 면 'YES' 를 출력 하고 그렇지 않 으 면' NO '를 출력 한다.
Sample Input
1
5 5 14
S*#*.
.#...
.....
****.
...#.
..*.P
#.*..
***..
...*.
*.#..
Sample Output
YES
Source
HDU 2007-6 Programming Contest
분석: 약간 구덩이, 순수 bfs.
1: 출발점 과 종점 은 임의의 위치 에 있 을 수 있 습 니 다. 제목 은 0, 0, 0, 엄마 알 입 니 다.
2: 양쪽 이 모두 전송 문 일 때 나 한쪽 이 전송 문 일 때 벽 일 때 이 두 가지 상황 은 죽음 이다.
코드:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int time,n,m,ec,ex,ey,vis[2][20][20];
// S 0,0,0
int sc,sx,sy;
int fx[4][2]={0,1,1,0,0,-1,-1,0};
char map[2][20][20],tt[20];
struct node
{
int c,x,y,step;
};
int check(node p)
{
if(p.c<0||p.c>1||p.x<0||p.y<0||p.x>=n||p.y>=m) return 0;
if(vis[p.c][p.x][p.y])return 0;
// ,
if(map[p.c][p.x][p.y]=='#'&&map[!p.c][p.x][p.y]!='*'&&map[!p.c][p.x][p.y]!='#') return 1;
if(map[p.c][p.x][p.y]=='.'||map[p.c][p.x][p.y]=='P')return 1;
return 0;
}
int bfs()
{
queue<node>Q;
node t,p;
t.c=sc;
t.x=sx;
t.y=sy;
t.step=0;
Q.push(t);
while(!Q.empty())
{
t=Q.front();
Q.pop();
if(t.c==ec&&t.x==ex&&t.y==ey) return t.step;
for(int i=0;i<4;i++)
{
p.c=t.c;
p.x=t.x+fx[i][0];
p.y=t.y+fx[i][1];
p.step=t.step+1;
if(check(p)&&p.step<=time)
{
if(map[p.c][p.x][p.y]=='#')
{
vis[p.c][p.x][p.y]=1;
p.c=!p.c;
}
Q.push(p);
vis[p.c][p.x][p.y]=1;
}
}
}
return -1;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(vis,0,sizeof(vis));
scanf("%d%d%d",&n,&m,&time);
for(int i=0;i<n;i++)
{
scanf("%s",map[0][i]);
for(int j=0;map[0][i][j];j++)
{
if(map[0][i][j]=='P'){ex=i;ey=j;ec=0;}
if(map[0][i][j]=='S'){sx=i;sy=j;sc=0;}
}
}
for(int i=0;i<n;i++)
{
scanf("%s",map[1][i]);
for(int j=0;map[1][i][j];j++)
{
if(map[1][i][j]=='P'){ex=i;ey=j;ec=1;}
if(map[1][i][j]=='S'){sx=i;sy=j;sc=1;}
}
}
if(bfs()!=-1) printf("YES
");
else printf("NO
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
제1 6 장 파일 에서 텍스트 검색 도구: grep 명령 과 egrep 명령제1 6 장 파일 에서 텍스트 검색 도구: grep 명령 과 egrep 명령 옵션 grep 명령 파일 에서 단 어 를 검색 하면 명령 은 "match pattern"을 포함 하 는 텍스트 줄 을 되 돌려 줍 니 다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.