題目不用解釋了，給出箱子的箱子的終點(diǎn)，求箱子的起點(diǎn)以及人的起點(diǎn)，使得人把箱子推到終點(diǎn)需要的最長步數(shù)。
我是從終點(diǎn)向起點(diǎn)DP的，就要考慮一種特殊情況：箱子開始就只能在終點(diǎn)，不可能在其他任何位置。
狀態(tài)轉(zhuǎn)移比較麻煩，分為8種情況，詳情看代碼吧
1
# include <iostream>
2# include <cstring>
3# include <queue>
4using namespace std;
5# define encode(r1,c1,r2,c2) (((((((r1)<<5)|(c1))<<5)|(r2))<<5)|(c2))
6# define getr1(pos) ((pos)>>15)
7# define getc1(pos) (((pos)>>10)&31)
8# define getr2(pos) (((pos)>>5)&31)
9# define getc2(pos) ((pos)&31)
10# define legal(r,c) (map[r][c]!='#')
11# define equal(r1,c1,r2,c2) ((r1)==(r2)&&(c1)==(c2))
12# define max(a,b) ((a)>(b)?(a):(b))
13int dp[2000000],n;
14char map[30][30];
15queue<int> q;
16int solve(int r,int c)
17
{
18
int res=0;
19 if(r!=n-1&&map[r+1][c]!='#')
20
{
21 dp[encode(r,c,r+1,c)]=0;
22 q.push(encode(r,c,r+1,c));
23
}
24 if(r!=0&&map[r-1][c]!='#')
25 {
26 dp[encode(r,c,r-1,c)]=0;
27 q.push(encode(r,c,r-1,c));
28 }
29 if(c!=0&&map[r][c-1]!='#')
30 {
31 dp[encode(r,c,r,c-1)]=0;
32 q.push(encode(r,c,r,c-1));
33 }
34 if(c!=n-1&&map[r][c+1]!='#')
35 {
36 dp[encode(r,c,r,c+1)]=0;
37 q.push(encode(r,c,r,c+1));
38 }
39 while(!q.empty())
40 {
41 int boxr=getr1(q.front()),boxc=getc1(q.front()),perr=getr2(q.front()),perc=getc2(q.front());
42 if(!equal(r,c,boxr,boxc))res=max(res,dp[q.front()]);
43 q.pop();
44 if(perr!=n-1&&map[perr+1][perc]!='#'&&!equal(boxr,boxc,perr+1,perc)&&dp[encode(boxr,boxc,perr+1,perc)]==-1)
45 {
46 dp[encode(boxr,boxc,perr+1,perc)]=dp[encode(boxr,boxc,perr,perc)]+1;
47 q.push(encode(boxr,boxc,perr+1,perc));
48 }
49 if(perr!=0&&map[perr-1][perc]!='#'&&!equal(boxr,boxc,perr-1,perc)&&dp[encode(boxr,boxc,perr-1,perc)]==-1)
50 {
51 dp[encode(boxr,boxc,perr-1,perc)]=dp[encode(boxr,boxc,perr,perc)]+1;
52 q.push(encode(boxr,boxc,perr-1,perc));
53 }
54 if(perc!=0&&map[perr][perc-1]!='#'&&!equal(boxr,boxc,perr,perc-1)&&dp[encode(boxr,boxc,perr,perc-1)]==-1)
55 {
56 dp[encode(boxr,boxc,perr,perc-1)]=dp[encode(boxr,boxc,perr,perc)]+1;
57 q.push(encode(boxr,boxc,perr,perc-1));
58 }
59 if(perc!=n-1&&map[perr][perc+1]!='#'&&!equal(boxr,boxc,perr,perc+1)&&dp[encode(boxr,boxc,perr,perc+1)]==-1)
60 {
61 dp[encode(boxr,boxc,perr,perc+1)]=dp[encode(boxr,boxc,perr,perc)]+1;
62 q.push(encode(boxr,boxc,perr,perc+1));
63 }
64 if(equal(boxr,boxc,perr+1,perc)&&perr!=0&&map[perr-1][perc]!='#'&&dp[encode(boxr-1,boxc,perr-1,perc)]==-1)
65 {
66 dp[encode(boxr-1,boxc,perr-1,perc)]=dp[encode(boxr,boxc,perr,perc)]+1;
67 q.push(encode(boxr-1,boxc,perr-1,perc));
68 }
69 if(equal(boxr,boxc,perr-1,perc)&&perr!=n-1&&map[perr+1][perc]!='#'&&dp[encode(boxr+1,boxc,perr+1,perc)]==-1)
70 {
71 dp[encode(boxr+1,boxc,perr+1,perc)]=dp[encode(boxr,boxc,perr,perc)]+1;
72 q.push(encode(boxr+1,boxc,perr+1,perc));
73 }
74 if(equal(boxr,boxc,perr,perc+1)&&perc!=0&&map[perr][perc-1]!='#'&&dp[encode(boxr,boxc-1,perr,perc-1)]==-1)
75 {
76 dp[encode(boxr,boxc-1,perr,perc-1)]=dp[encode(boxr,boxc,perr,perc)]+1;
77 q.push(encode(boxr,boxc-1,perr,perc-1));
78 }
79 if(equal(boxr,boxc,perr,perc-1)&&perc!=n-1&&map[perr][perc+1]!='#'&&dp[encode(boxr,boxc+1,perr,perc+1)]==-1)
80 {
81 dp[encode(boxr,boxc+1,perr,perc+1)]=dp[encode(boxr,boxc,perr,perc)]+1;
82 q.push(encode(boxr,boxc+1,perr,perc+1));
83 }
84 }
85 return res;
86
}
87int main()
88{
89 memset(dp,-1,sizeof(dp));
90 cin>>n;
91 for(int i=0;i<n;i++)
92 cin>>map[i];
93 int tr,tc;
94 for(int i=0;i<n;i++)
95 for(int j=0;j<n;j++)
96 if(map[i][j]=='*')
97 {
98 tr=i;
99 tc=j;
100 goto endloop;
101 }
102endloop:;
103 // if(n==2)
104 // cout<<0<<endl;
105 // else
106 cout<<solve(tr,tc)<<endl;
107 return 0;
108}
109
110