hdu 1254 推箱子

首先按箱子进行BFS.  然后判断箱子所走方向的反面，人是否能到达，即对人进行DFS。。

下面是 AC代码：

[cpp] 
#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; 
 
} 

补充：软件开发 , C++ ,

上一个：POJ1679 The Unique MST
下一个：light oj 1257 树的直径