Broken robot

On the first line you will be given two space separated integers N and M $(1 \leq N, M \leq 1000)$ . On the second line you will be given another two space separated integers i and j $(1 \leq i \leq N, 1 \leq j \leq M)$ — the number of the initial row and the number of the initial column. Note that, (1, 1) is the upper left corner of the board and (N, M) is the bottom right corner.

C++(g++ 7.5.0) 解法, 执行用时: 36ms, 内存消耗: 14332K, 提交时间: 2022-08-11 11:00:00

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,x,y;
double a[N][N],f[N][N];
int main(){
	scanf("%d%d",&n,&m);
	scanf("%d%d",&x,&y);
	for(int i=1;i<=m;i++)f[n][i]=0;
	for(int o=n-1;o>=1;o--){
		
		for(int i=1;i<=m;i++){
		a[i][i]=3;a[i][i-1]=a[i][i+1]=-1;
		if(i==1)a[i][i]--;
		if(i==m)a[i][i]--;
		a[i][m+1]=4+f[o+1][i];
		if(i==1)a[i][m+1]--;
		if(i==m)a[i][m+1]--;
	}
	for(int i=1;i<=m;i++){
		if(a[i][i]==0){
			printf("No Solution\n");
			return 0;
		}
		else{
			if(i!=m)a[i][i+1]=a[i][i+1]/a[i][i];
			a[i][m+1]=a[i][m+1]/a[i][i];
			a[i][i]=1;
			if(i!=m){
				a[i+1][i+1]=a[i+1][i+1]-a[i+1][i]*a[i][i+1];
				a[i+1][m+1]=a[i+1][m+1]-a[i+1][i]*a[i][m+1];
				a[i+1][i]=0;
			}
		}
	}
	for(int i=m;i>=1;i--){
		f[o][i]=a[i][m+1];
		if(i!=1)a[i-1][m+1]-=a[i-1][i]*f[o][i];
	}
	}
	printf("%.4lf\n",f[x][y]);
	return 0;
}

C++(clang++11) 解法, 执行用时: 709ms, 内存消耗: 8048K, 提交时间: 2021-03-24 15:38:56

#include<cstdio>
double dp[1005][1005];
int main(){
	int n,m,x,y,i,j,t;
	scanf("%d%d%d%d",&n,&m,&x,&y);
	for(i=n-1;i>=x;--i)
		for(t=1;t<=100;++t)//循环50次就好
			if(m==1)
				dp[i][1]=(dp[i][1]+dp[i+1][1])/2.0+1;
                else{
				dp[i][1]=(dp[i][1]+dp[i][2]+dp[i+1][1])/3.0+1;
				dp[i][m]=(dp[i][m]+dp[i][m-1]+dp[i+1][m])/3.0+1;
				for(j=2;j<m;++j)
					dp[i][j]=(dp[i][j]+dp[i][j-1]+dp[i][j+1]+dp[i+1][j])/4.0+1;
			}
	printf("%.4lf\n",dp[x][y]);//本人实测可过！
	return 0;
}

详情