hdu 1254 푸 시 상자
우선 상자 별로 BFS 를 진행 합 니 다. 그리고 상자 가 가 는 방향의 반대편, 사람 이 도착 할 수 있 는 지, 즉 사람 에 대해 DFS 를 진행 하 는 지 를 판단 한다.
다음은 AC 코드 입 니 다.
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int MAX = 10;
int map[MAX][MAX];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
int other_dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}}; //
bool vis[MAX][MAX][MAX][MAX];
bool mark[MAX][MAX];
int flag,ans;
struct node
{
int ps_x,ps_y;
int bk_x,bk_y;
int step;
int cur_map[MAX][MAX];
} s_pos;
int end_x,end_y;
int m,n;
void init()
{
s_pos.step=0;
for(int i=0; i<m; i++) for(int j=0; j<n; j++)
{
if(map[i][j]==2) s_pos.bk_x=i, s_pos.bk_y=j;
else if(map[i][j]==3) end_x=i,end_y=j;
else if(map[i][j]==4) s_pos.ps_x=i, s_pos.ps_y=j;
s_pos.cur_map[i][j]=map[i][j];
}
memset(vis,0,sizeof(vis));
}
bool cheak(int x,int y){
if(x>=0&&x<m&&y>=0&&y<n&&map[x][y]!=1) return true;
return false;
}
int can;
void dfs(int p_x,int p_y,int b_x,int b_y,int now_map[10][10]) //
{
if(can) return ;
if(p_x==b_x&&p_y==b_y) { can=1; return ;}//cout<<p_x<<" "<<p_y<<endl;
for(int i=0; i<4; i++){
int x=p_x+dir[i][0], y=p_y+dir[i][1];
if(cheak(x,y)&&now_map[x][y]!=2&&!mark[x][y]){
mark[x][y]=true; dfs(x,y,b_x,b_y,now_map; mark[x][y]=false;
}
}
}
void bfs()
{
init(); queue<node > q;
vis[s_pos.bk_x][s_pos.bk_y][s_pos.ps_x][s_pos.ps_y]=true;
q.push(s_pos);
while(!q.empty()){
node now = q.front();
q.pop();
if(now.bk_x==end_x&&now.bk_y==end_y){
flag=1,ans=now.step; return ;
}
for(int i=0; i<4; i++){
node next=now;
next.bk_x+=dir[i][0], next.bk_y+=dir[i][1];next.step+=1;
int x=now.bk_x+other_dir[i][0],y=now.bk_y+other_dir[i][1];
if(cheak(x,y)&&cheak(next.bk_x,next.bk_y)&&!vis[next.bk_x][next.bk_y][now.bk_x][now.bk_y])
{
memset(mark,0,sizeof(mark)); mark[next.ps_x][next.ps_y]=true;
can=0;
dfs(next.ps_x,next.ps_y,x,y,now.cur_map);
if(can){
vis[next.bk_x][next.bk_y][now.bk_x][now.bk_y]=true; // cout<<next.bk_x<<" "<<next.bk_y<<endl;
next.ps_x=now.bk_x;
next.ps_y=now.bk_y;
next.cur_map[next.bk_x][next.bk_y]=2;
next.cur_map[now.bk_x][now.bk_y]=0;
q.push(next);
}
}
}
}
}
int main()
{
int t,i,j;
cin>>t;
while(t--)
{
cin>>m>>n;
for(i=0; i<m; i++) for(j=0; j<n; j++) cin>>map[i][j];
flag=0;
ans=-1;
bfs();
if(flag) cout<<ans<<endl;
else cout<<-1<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.