「题解」洛谷 P7995 [USACO21DEC] Walking Home B
关于这一题，我们可以先考虑一下 广度优先搜索。
我们定义一个结构体，用它表示 当前状态下 的位置、转身次数、方向以及之前走过的路线。
广搜部分可以先套上模板，再慢慢修改。
#include
#define int long long
#define mkp make_pair
using namespace std;
int t,n,k,ans;
char s[55][55];
struct node
{
int x,y,cnt;
pairdir;
string way;
};
void bfs()
{
unordered_maproad;
queueq;
q.push((node){1,2,0,mkp(0,1),(string)"R"});
q.push((node){2,1,0,mkp(1,0),(string)"D"});
while(!q.empty())
{
node tmp=q.front();
q.pop();
int x=tmp.x,y=tmp.y,cnt=tmp.cnt,dx=tmp.dir.first,dy=tmp.dir.second;
string way=tmp.way;
if(cnt>k||s[x][y]=='H'||way.size()>n*n)
continue;
if(x==n&&y==n&&cnt<=k)
{
if(!road[way])
++ans,road[way]=1;
continue;
}
if(x+dx<=n&&y+dy<=n)
q.push((node){x+dx,y+dy,cnt,mkp(dx,dy),way+(dx?"D":"R")});
if(x+dy<=n&&y+dx<=n&&cnt 能拿下 50分。
提交记录
显然，我们需要一种更高效的方法。
其实，我们可以使用 动态规划 来解决这题。
设 \(dp_{x,y,k,d}\) 代表此时在格子 \((x,y)\)，已转弯 \(k\) 次，现在朝着方向 \(d\) 的路线数 (当 \(d=0\) 时，代表 向下，当 \(d=1\) 时，代表 向右)。
于是，我们可以从 左边的格子 和 上面的格子 转移到 当前格子，转移时需要考虑 是否转弯。
时间复杂度为 \(O(T\times n^2\times k)\)。
#include
#define int long long
using namespace std;
int t,n,k,dp[55][55][4][2];
char s[55][55];
signed main()
{
scanf("%lld",&t);
while(t--)
{
int ans=0;
memset(dp,0,sizeof dp);
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
dp[1][1][0][0]=dp[1][1][0][1]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(s[i][j]=='.')
{
for(int cnt=0;cnt<=k;cnt++)
{
dp[i][j][cnt][0]+=dp[i-1][j][cnt][0];
if(cnt)
dp[i][j][cnt][0]+=dp[i][j-1][cnt-1][1];
dp[i][j][cnt][1]+=dp[i][j-1][cnt][1];
if(cnt)
dp[i][j][cnt][1]+=dp[i-1][j][cnt-1][0];
}
}
}
}
for(int cnt=0;cnt<=k;cnt++)
ans+=dp[n-1][n][cnt][0]+dp[n][n-1][cnt][1];
printf("%lld\n",ans);
}
return 0;
}
提交记录