Description
有一幅n*n的方格图，n <=100，每个点上有一个值。
\从（1,1）出发，走到（n,n），只能走上下左右。
每走一步花费t，每走三步需要花费走完三步后到达格子的值。
求最小花费的值。
Input
Output
Sample Input
4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80
Sample Output
31
一开始看这题，感觉他有问题啊。。
每个数值没给QAQ，那怎么做啊。。
要是丧心病狂高精度怎么办。。
不管了。。
反正n是100，应该是一个搜索
那会不会有负权啊，要是有一个负环怎么办，-∞？
不管了，忽略这种情况。。
然后就随便敲了一个dfs+最优性剪枝。。
TLE了。。
#include<cstdio>
#include<cstring>
const int N=105;
int f[N][N][4];
int n,t;
int a[N][N];
int ans=1<<30;
void dfs (int x,int y,int z,int k)//当前在哪个格子 代价 已经是第几步了
{if (k==3) {k=0;z+=a[x][y];}if (z>=ans) return ;if (f[x][y][k]<=z) return ;if (x==n&&y==n) {ans=z;return ;}if (z+((n-x)+(n-y))*t>=ans) return ;f[x][y][k]=z;if (x<n) dfs(x+1,y,z+t,k+1);if (x>1) dfs(x-1,y,z+t,k+1);if (y<n) dfs(x,y+1,z+t,k+1);if (y>1) dfs(x,y-1,z+t,k+1);return ;
}
int main()
{memset(f,127,sizeof(f));scanf("%d%d",&n,&t);for (int u=1;u<=n;u++)for (int i=1;i<=n;i++)scanf("%d",&a[u][i]);dfs(1,1,0,0);printf("%d\n",ans);return 0;
}说好的暴力题呢。。
暴力题为什么卡了我的dfs。。
数据这么强？？？？？
我们仔细思考啊。。其实膜了一下TKJ
其实除了最后几步。。其他都等于只可以一次走三步。。
然后就又dfs一下。。
#include<cstdio>
#include<cstring>
const int N=105;
int f[N][N];
int n,t;
int a[N][N];
int px[16]={
0,1,2,3,2,1,0,-1,-2,-3,-2,-1,1,0,-1,0},py[16]={
3,2,1,0,-1,-2,-3,-2,-1,0,1,2,0,1,0,-1};
int px2[8]={
0,1,2,1,0,-1,-2,-1},py2[8]={
2,1,0,-1,-2,-1,0,1},px1[4]={
1,0,-1,0},py1[4]={
0,1,0,-1};
void dfs (int x,int y,int z)//当前在哪个格子 代价 已经是第几步了
{if (f[x][y]<=z) return ;f[x][y]=z;for(int i=0;i<16;i++){int xx=x+px[i],yy=y+py[i];if(xx>0&&xx<=n&&yy>0&&yy<=n)dfs(xx,yy,z+t*3+a[xx][yy]);}return ;
}
int main()
{memset(f,127,sizeof(f));scanf("%d%d",&n,&t);for (int u=1;u<=n;u++)for (int i=1;i<=n;i++)scanf("%d",&a[u][i]);dfs(1,1,0);for(int i=0;i<8;i++){int x=n+px2[i],y=n+py2[i];if(x>0&&x<=n&&y>0&&y<=n&&f[n][n]>f[x][y]+t*2)f[n][n]=f[x][y]+t*2;}for(int i=0;i<4;i++){int x=n+px1[i],y=n+py1[i];if(x>0&&x<=n&&y>0&&y<=n&&f[n][n]>f[x][y]+t)f[n][n]=f[x][y]+t;}printf("%d",f[n][n]);return 0;
}然后发现一定要写bfs才可以。。
CODE from TKJ
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;int n,dis[110][110],mp[110][110],t;
bool v[110][110];
int px[16]={
0,1,2,3,2,1,0,-1,-2,-3,-2,-1,1,0,-1,0},py[16]={
3,2,1,0,-1,-2,-3,-2,-1,0,1,2,0,1,0,-1},px2[8]={
0,1,2,1,0,-1,-2,-1},py2[8]={
2,1,0,-1,-2,-1,0,1},px1[4]={
1,0,-1,0},py1[4]={
0,1,0,-1};int main()
{scanf("%d%d",&n,&t);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&mp[i][j]);if(n<=2){printf("%d",t*(n*2-2));return 0;}queue<int>qx,qy;qx.push(1);qy.push(1);v[1][1]=1;memset(dis,63,sizeof(dis));dis[1][1]=0;while(!qx.empty()){int x=qx.front(),y=qy.front();v[x][y]=0;for(int i=0;i<16;i++){int xx=x+px[i],yy=y+py[i];if(xx>0&&xx<=n&&yy>0&&yy<=n&&dis[xx][yy]>dis[x][y]+t*3+mp[xx][yy]){dis[xx][yy]=dis[x][y]+t*3+mp[xx][yy];if(!v[xx][yy]){qx.push(xx);qy.push(yy);v[xx][yy]=1;}}}qx.pop();qy.pop();}for(int i=0;i<8;i++){int x=n+px2[i],y=n+py2[i];if(x>0&&x<=n&&y>0&&y<=n&&dis[n][n]>dis[x][y]+t*2)dis[n][n]=dis[x][y]+t*2;}for(int i=0;i<4;i++){int x=n+px1[i],y=n+py1[i];if(x>0&&x<=n&&y>0&&y<=n&&dis[n][n]>dis[x][y]+t)dis[n][n]=dis[x][y]+t;}printf("%d",dis[n][n]);
}