Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
1.3 kB
1
Indexable
Never
#include <iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<numeric>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;
	int y[251][251];
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			char number;
			cin >> number;
			y[i][j] = number - '0';
		}
	}
	int s[251][251];
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			s[i][j] = 0;
		}
	}
	int k = 0;
	for (int i = 1; i <= n; i++)
	{
		k = k + y[1][i];
		y[1][i] = k;
		s[1][i] = k;
	}
	k = 0;
	for (int i = 1; i <= n; i++)
	{
		k = k + y[i][1];
		s[i][1] = k;
		y[i][1] = k;
	}
	k = y[2][2];
	int l ;
	int d;
	for (l=2 ;l <= n; l++)
	{
		for ( d = 2; d <= n; d++)
		{
			k = y[l][d];
			if(k+s[l][d-1]>=k+s[l-1][d])
			{
				k = k + s[l - 1][d];
			    s[l][d] = k;
			}
			else
			{
				k = k + s[l][d-1];
				s[l][d] = k;
			}
		}
	}
	char p[251][251];
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			p[i][j] = '.';
		}
	}
     d = n;
	 l = n;
	while (l != 1 && d != 1)
	{
		k = s[l][d];
		if (k + s[l - 1][d] >= k + s[l][d - 1])
		{
			p[l][d - 1] ='#';
			d--;
		}
		else
		{
			p[l - 1][d] = '#';
			l--;
		}
	}
	p[n][n] = '#';
	p[1][1] = '#';
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cout << p[i][j];
		}
		cout<<'\n';
	}
}
Leave a Comment