编程题1

#include <bits/stdc++.h>
using namespace std;
int n,m;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int vis[50][50][50][50];
vector<string> view;
struct node{
        int a_x,a_y,b_x,b_y,step;
        node(int a_x,int a_y,int b_x,int b_y,int step):
                a_x(a_x),a_y(a_y),b_x(b_x),b_y(b_y),step(step){};

};
bool isTrue(int x,int y)
{
        if(x<0||y<0||x>=n||y>=m||view[x][y]=='#')
                return false;
        return true;
}
int bfs(int start_x,int start_y,int box_x,int box_y)
{
        queue<node> ans;
        ans.push(node(start_x,start_y,box_x,box_y,0));
        vis[start_x][start_y][box_x][box_y]=1;
        while(!ans.empty())
        {
                node p=ans.front();
                ans.pop();
                int ax=p.a_x;
                int ay=p.a_y;
                int bx=p.b_x;
                int by=p.b_y;
                int step=p.step;
                for(int i=0;i<4;i++)
                {
                        int new_ax=ax+dir[i][0];
                        int new_ay=ay+dir[i][1];
                        int new_bx=bx+dir[i][0];
                        int new_by=by+dir[i][1];
                        if(!isTrue(new_ax,new_ay))
                                continue;
                        //移动到箱子前
                        if((new_ax!=bx||new_ay!=by)&&vis[new_ax][new_ay][bx][by]==0)
                        {
                                vis[new_ax][new_ay][bx][by]=1;
                                ans.push(node(new_ax,new_ay,bx,by,step+1));
                        }
                        //人和箱子一起移动
                        else if(new_ax==bx&&new_ay==by&&isTrue(new_bx,new_by)&&vis[new_ax][new_ay][new_bx][new_by]==0)
                        {
                                vis[new_ax][new_ay][new_bx][new_by]==1;
                                if(view[new_bx][new_by]=='E')
                                        return step+1;
                                ans.push(node(new_ax,new_ay,new_bx,new_by,step+1));
                        }

                }
        }
        return -1;

}
int main() {
        memset(vis,-0,sizeof(vis));
        cin>>n>>m;
        view=vector<string> (n,string(""));
        for(int i=0;i<n;i++)
                cin>>view[i];
        int start_x,start_y,box_x,box_y;
        for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
                {
                        if(view[i][j]=='S')
                                start_x=i,start_y=j;
                        else if(view[i][j]=='0')
                                box_x=i,box_y=j;
                }
        cout<<bfs(start_x,start_y,box_x,box_y)<<endl;
    return 0;
}

#include<iostream>
#include<queue>

using namespace std;

int m,n;
int sx,sy;
int bx,by;
char a[52][52];
int dp[52][52][52][52];
int mov[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

int main(){
    cin>>n>>m;
    for(int i=0;i<52;i++){
        for(int j=0;j<52;j++){
            a[i][j]='#';
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='S'){
                sx=i;
                sy=j;
            }
            if(a[i][j]=='0'){
                bx=i;
                by=j;
            }
        }
    }
    queue<vector<int>> q;
    vector<int> tmp={sx,sy,bx,by};
    q.push(tmp);
    int x,y,xb,yb,xn,yn;
    while(!q.empty()){
        vector<int> tmp = q.front();
        x=tmp[0],y=tmp[1],xb=tmp[2],yb=tmp[3];
        q.pop();
        for(int i=0;i<4;i++){
            xn=x+mov[i][0];
            yn=y+mov[i][1];
            if(xn!=xb || yn!=yb){
                if(a[xn][yn]!='#'&&dp[xn][yn][xb][yb]==0){
                    dp[xn][yn][xb][yb] = dp[x][y][xb][yb]+1;
                    vector<int> tmp2={xn,yn,xb,yb};
                    q.push(tmp2);
                }
            }
            else{
                int xbn=xb+mov[i][0];
                int ybn=yb+mov[i][1];
                if(a[xbn][ybn]!='#'&&dp[xn][yn][xbn][ybn]==0){
                    dp[xn][yn][xbn][ybn] = dp[x][y][xb][yb]+1;
                    if(a[xbn][ybn]=='E'){
                        cout<<dp[xn][yn][xbn][ybn]<<endl;
                        return 0;
                    }
                    vector<int> tmp2={xn,yn,xbn,ybn};
                    q.push(tmp2);
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

n,m=[int(i) for i in input().split()]
map1=[]
for i in range(n):
    map1+=[i for i in input().split()]

point=[[] for i in range(3)]
state_box=[[float('inf')]*m for i in range(n)]
state_worker=[[float('inf')]*m for i in range(n)]
res=0
for i in range(n):
    for j in range(m):
        if map1[i][j]=='E':
            point[0]=[i,j]
        elif map1[i][j]=='0':
            point[1] = [i, j]
        elif map1[i][j]=='S':
            point[2]=[i,j]
def DFS(i,j,deep,object,state_matrix):
    if i<0 or j<0 or i>=n or j>=m:
        return 0
    if map1[i][j]=='#':
        return 0
    if state_matrix[i][j]<=deep:
        return 1
    state_matrix[i][j] = deep
    a1=DFS(i-1,j,deep+1,object,state_matrix)
    a2=DFS(i+1,j,deep+1,object,state_matrix)
    a3=DFS(i,j-1,deep+1,object,state_matrix)
    a4=DFS(i,j+1,deep+1,object,state_matrix)
    if object=='box':
        if (a1*a2)+(a3*a4)==0:    #排除箱子被推到角落去的情况
            state_matrix[i][j] = float('inf')
    return 1
DFS(point[0][0],point[0][1],0,'box',state_box)#create box state map
if state_box[point[1][0]][point[1][1]]==float('inf'):
    print(-1)
else:
    res+=state_box[point[1][0]][point[1][1]]
DFS(point[1][0],point[1][1],0,'worker',state_worker)
if state_worker[point[2][0]][point[2][1]]==float('inf'):
    print(-1)
res+=state_worker[point[2][0]][point[2][1]]-1
res+=2
print(res)