Word Wrap Problem (text justification)

Resources:

Tushar Roy Video 

 LeetCode Video

MIT Lecture 

Github link 

Code:

 

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	int print(int p[], int n)
	{
	int x;
	if (p[n] == 1) x = 1;
	else x = print(p, p[n] - 1) + 1;
	cout << "Line Number " << x << ": From word no. " << p[n] << " to " << n << endl;
	return x;
	}
	//O(n^2)
	void solveWordWrap(int l[], int n, int m)
	{
	int extras[n + 1][n + 1];
	int lc[n + 1][n + 1]; //
	int c[n + 1]; // total cost
	int p[n + 1]; // for print solution
	// calculate extra spaces in a single line. The value extra[i][j]
	// indicates extra spaces if words from word number i to j are
	// placed in a single line
	for (int i = 1; i <= n; i++) {
	extras[i][i] = m - l[i - 1];
	for (int j = i + 1; j <= n; j++) {
	extras[i][j] = extras[i][j - 1] - l[j - 1] - 1;
	}
	}
	// Calculate line cost corresponding to the above calculated extra
	// spaces. The value lc[i][j] indicates cost of putting words from
	// word number i to j in a single line
	for (int i = 1; i <= n; i++) {
	for (int j = i; j <= n; j++) {
	if (extras[i][j] < 0) lc[i][j] = INT_MAX;
	else if (j == n && extras[i][j] >= 0)
	lc[i][j] = 0;
	else lc[i][j] = extras[i][j] * extras[i][j];
	}
	}
	/// minCost
	c[0] = 0;
	for (int j = 1; j <= n; j++) {
	c[j] = INT_MAX;
	for (int i = 1; i <= j; i++) {
	if (c[i - 1] != INT_MAX && lc[i][j] != INT_MAX && (c[i - 1] + lc[i][j] < c[j])) {
	c[j] = c[i - 1] + lc[i][j];
	p[j] = i;
	}
	}
	}
	print(p, n);
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int len[] = {3, 2, 2, 5};// per word length
	int n = sizeof(len) / sizeof(len[0]);
	int m = 6; // every line length
	solveWordWrap(len, n, m);//text justification
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw Word Wrap Problem.cpp hosted with ❤ by GitHub

Share: