RT,跟std对拍一切正常,没拍出问题/kk。
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "algorithm"
#include "queue"
#include "cmath"
#include "vector"
#include "map"
#include "time.h"
#define data_of_qwq (gtdt(a[i][j + 1], i, j + 1) + gtdt(a[i + 1][j], i + 1, j))
#define data1 (gtdt(a[i][j + 1], i, j + 1))
#define data2 (gtdt(a[i + 1][j], i + 1, j))
#define data3 (gtdt(a[i][j - 1], i, j - 1))
#define data4 (gtdt(a[i - 1][j], i - 1, j))
using namespace std;
int h,w;
char a[1010][1010];
char gt(){
char c = getchar();
while((c < '0' || c > '9') && c !='.')
c = getchar();
return c;
}
int gtdt(char c,int x = 0,int y = 0){
if(c == '.')
return 0;
// printf("%d-%d-%d ", c, x, y);
return c - '0';
}
int dp[1010][1010][3][3];
char e[1010];
//三维: 0.无 ,1. 左下 , 2.右上
//四维: 0.无 ,1. 右 , 2.下
signed main(){
scanf("%lld%lld",&h,&w);/*
for(int i = 1; i <= h ; i++)
for(int j = 1; j <= w; j++)
a[i][j] = gt();*/
for(int i = 1; i <= h ; i++)
{
scanf("%s", e + 1);
for(int j = 1;j <= w; j++)
a[i][j] = e[j];
}
memset(dp,0x7f7f,sizeof(dp));
dp[1][1][0][0] = (gtdt(a[1][1]) + gtdt(a[1 + 1][1]) + gtdt(a[1][1 + 1]));
dp[1][1][0][1] = (gtdt(a[1][1]) + gtdt(a[1][1 + 1]));
dp[1][1][0][2] = (gtdt(a[1][1]) + gtdt(a[1 + 1][1]));
for(int i = 1; i <= h; i++)
a[i][w + 1] = a[i][0] = '.';
for(int i = 1; i <= w; i++)
a[h + 1][i] = a[0][i] = '.';
/* for(int i = 1; i <= h + 1 ; i++){
for(int j = 1; j <= w + 1; j++)
cout << a[i][j];
cout <<"\n";
}*/
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
if(i == 1 && j == 1)
continue;
if(i > 1){
dp[i][j][0][0] = min(dp[i][j][0][0], dp[i - 1][j][2][2] + data_of_qwq);
dp[i][j][0][0] = min(dp[i][j][0][0], dp[i - 1][j][1][2] + data_of_qwq);
dp[i][j][0][0] = min(dp[i][j][0][0], dp[i - 1][j][0][2] + data_of_qwq);
dp[i][j][0][1] = min(dp[i][j][0][1], dp[i - 1][j][0][2] + data1 + (data2 ? data3 : 0));
dp[i][j][0][1] = min(dp[i][j][0][1], dp[i - 1][j][2][2] + data1 + (data2 ? data3 : 0));
dp[i][j][0][1] = min(dp[i][j][0][1], dp[i - 1][j][1][2] + data1);
dp[i][j][0][2] = min(dp[i][j][0][2], dp[i - 1][j][0][2] + data2 + (data1 ? data3 : 0));
dp[i][j][0][2] = min(dp[i][j][0][2], dp[i - 1][j][2][2] + data2 + (data1 ? data3 : 0));
dp[i][j][0][2] = min(dp[i][j][0][2], dp[i - 1][j][1][2] + data2);
dp[i][j][2][0] = min(dp[i][j][2][0], dp[i - 1][j][0][0] + data_of_qwq);
dp[i][j][2][0] = min(dp[i][j][2][0], dp[i - 1][j][1][0] + data_of_qwq);
dp[i][j][2][0] = min(dp[i][j][2][0], dp[i - 1][j][2][0] + data_of_qwq);
dp[i][j][2][1] = min(dp[i][j][2][1], dp[i - 1][j][0][0] + data1 + (data2 ? data3 : 0));
dp[i][j][2][1] = min(dp[i][j][2][1], dp[i - 1][j][2][0] + data1 + (data2 ? data3 : 0));
dp[i][j][2][1] = min(dp[i][j][2][1], dp[i - 1][j][1][0] + data1);
dp[i][j][2][2] = min(dp[i][j][2][2], dp[i - 1][j][0][0] + data2 + (data1 ? data3 : 0));
dp[i][j][2][2] = min(dp[i][j][2][2], dp[i - 1][j][2][0] + data2 + (data1 ? data3 : 0));
dp[i][j][2][2] = min(dp[i][j][2][2], dp[i - 1][j][1][0] + data2);
}
if(j > 1){
dp[i][j][0][0] = min(dp[i][j][0][0], dp[i][j - 1][2][1] + data_of_qwq);
dp[i][j][0][0] = min(dp[i][j][0][0], dp[i][j - 1][1][1] + data_of_qwq);
dp[i][j][0][0] = min(dp[i][j][0][0], dp[i][j - 1][0][1] + data_of_qwq);
dp[i][j][0][1] = min(dp[i][j][0][1], dp[i][j - 1][0][1] + data1 + (data2 ? data4 : 0));
dp[i][j][0][1] = min(dp[i][j][0][1], dp[i][j - 1][1][1] + data1 + (data2 ? data4 : 0));
dp[i][j][0][1] = min(dp[i][j][0][1], dp[i][j - 1][2][1] + data1);
dp[i][j][0][2] = min(dp[i][j][0][2], dp[i][j - 1][0][1] + data2 + (data1 ? data4 : 0));
dp[i][j][0][2] = min(dp[i][j][0][2], dp[i][j - 1][1][1] + data2 + (data1 ? data4 : 0));
dp[i][j][0][2] = min(dp[i][j][0][2], dp[i][j - 1][2][1] + data2);
dp[i][j][1][0] = min(dp[i][j][1][0], dp[i][j - 1][0][0] + data_of_qwq);
dp[i][j][1][0] = min(dp[i][j][1][0], dp[i][j - 1][1][0] + data_of_qwq);
dp[i][j][1][0] = min(dp[i][j][1][0], dp[i][j - 1][2][0] + data_of_qwq);
dp[i][j][1][1] = min(dp[i][j][1][1], dp[i][j - 1][0][0] + data1 + (data2 ? data4 : 0));
dp[i][j][1][1] = min(dp[i][j][1][1], dp[i][j - 1][1][0] + data1 + (data2 ? data4 : 0));
dp[i][j][1][1] = min(dp[i][j][1][1], dp[i][j - 1][2][0] + data1);
dp[i][j][1][2] = min(dp[i][j][1][2], dp[i][j - 1][0][0] + data2 + (data1 ? data4 : 0));
dp[i][j][1][2] = min(dp[i][j][1][2], dp[i][j - 1][1][0] + data2 + (data1 ? data4 : 0));
dp[i][j][1][2] = min(dp[i][j][1][2], dp[i][j - 1][2][0] + data2);
}
}
}
cout << min(dp[h][w][0][0], min(dp[h][w][1][0], min(dp[h][w][2][0], min(dp[h][w][2][1], min(dp[h][w][1][1], min(dp[h][w][0][1], min(dp[h][w][2][2], min(dp[h][w][1][2], dp[h][w][0][2])))))))) << "\n";
return 0;
}