回家问题题解
【前言】
比较难的题目。
【暴力】
每次搜索最佳路径。
复杂度很大。
【正解】
正难则反。
把问题变成，牛牛要按顺序出村子，尽量不经过有其他牛牛的位置。
考虑一个优美一点的暴力，假设我们知道当前每个点出发离开网格时的最小内疚值，一个牛牛出村子可能会影响一些牛牛的答案，我们就暴力地更新，这样做最坏情况看起来是O(n^4)的，因为假设每个点都会影响很多点，似乎是会达到上界的。
但我们再将牛牛出村子带来的影响量化，很直观的，只会使一部分其他牛牛出村子的答案-1，对于不改变答案的点，它及其它可能延伸的后继都是没必要去遍历的，所以最终复杂度应该是和最初始情况下牛牛们的答案的和有关，大概O(n^3)，可能还很不满，足以通过500的数据。
参考代码：
class Solution {
public:
/**
*
* @param n int整型
* @param m int整型
* @param c int整型二维数组
* @param cRowLen int c数组行数
* @param cColLen int* c数组列数
* @return int整型
*/int nn,mm;
int fl[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int a[300000],b[300000],f[1000][1000];
void dfs(int x,int y)
{
for (int i=0;i<=3;i++)
{
int xx=x+fl[i][0],yy=y+fl[i][1];
if (xx>0&&xx<=nn&&yy>0&&yy<=mm&&f[xx][yy]>f[x][y])
{
f[xx][yy]=f[x][y];
dfs(xx,yy);
}
}
}
int wwork(int n, int m, int** c, int cRowLen, int* cColLen) {
// write code here
nn=n;mm=m;
for (int i=0;i<n*m;i++)
{
a[n*m-i]=c[i][0];
b[n*m-i]=c[i][1];
}
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) f[i][j]=min(min(i-1,n-i),min(j-1,m-j));
int ans=0;
for (int i=1;i<=n*m;i++)
{
ans=ans+f[a[i]][b[i]];
dfs(a[i],b[i]);
}
return ans;
}
};
查看13道真题和解析