Linear DataStructures: 2D array problems

Problems:

Here are some problems based on 2D arrays.

• UVa 00101 - The Blocks Problem
• UVa 00434 - Matty’s Blocks
• UVa 00466 - Mirror Mirror
• UVa 00541 - Error Correction
• UVa 10016 - Flip-flop the Squarelotron
• UVa 10703 - Free spots
• UVa 10855 - Rotated squares *
• UVa 10920 - Spiral Tap *
• UVa 11040 - Add bricks in the wall
• UVa 11349 - Symmetric Matrix
• UVa 11360 - Have Fun with Matrices
• UVa 11581 - Grid Successors *
• UVa 11835 - Formula 1
• UVa 12187 - Brothers
• UVa 12291 - Polyomino Composer
• UVa 12398 - NumPuzz I

Here is the link to the problems: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=624

Here are my solution and hints to some of these problems

Hint and solutions:

Uva 00541: Error Correction

Simple, no special algorithm. Do as asked. Count the number of 1s for each row and column. All of them must be even. If the contain odd, the number of such cases must not be greater than 1, else it is corrupt.

When one odd exist in both rows and columns, the difference of these sums must be a multiple of two(if you turn a bit, you increase one and decrease other), otherwise, it is again a corrupt case.

#include <bits/stdc++.h>
	using namespace std;
	int main(int argc, char const *argv[]) {
	int n;
	while(scanf("%d", &n), n!=0){
	bool arr[n][n];
	for(int i=0;i<n;i++){
	for (size_t j = 0; j < n; j++) {
	int temp;
	scanf("%d", &temp);
	arr[i][j] = temp;
	}
	}
	int i=0, j=0;
	int cols[n]={0};
	int rows[n]={0};
	for (i = 0; i < n; i++) {
	int sum1 = 0;
	int sum = 0;
	for (j = 0; j < n; j++) {
	sum1 += arr[i][j];
	sum += arr[j][i];
	}
	cols[i] = sum;
	rows[i]= sum1;
	}
	int counti = 0;
	int countj=0;
	int x=0, y=0;
	int temp1=0;
	int temp2=0;
	for (size_t i = 0; i < n; i++) {
	if(counti>1||countj>1){
	break;
	}
	if(cols[i]%2==1){
	counti++;
	x=i;
	}
	if(rows[i]%2==1){
	countj++;
	y=i;
	}
	}
	if(counti>1||countj>1){
	std::cout << "Corrupt" << '\n';
	continue;
	}
	if(counti==0&&countj==0){
	std::cout << "OK" << '\n';
	continue;
	}
	if(abs(rows[y]-cols[x])%2==0)
	std::cout << "Change bit "<<'('<<y+1<<','<<x+1<<')' << '\n';
	else
	std::cout << "Corrupt" << '\n';
	}
	return 0;
	}

Uva 10703-Free spots

Basic, use a 2D array and store ones and zeros in it.

int main(int argc, char const *argv[]) {
	int W, H, N;
	while (scanf("%d %d %d", &W, &H, &N)==3) {
	if(W==0&&H==0&&N==0)
	break;
	bool arr[W+1][H+1]={0};//all empty
	for (size_t i = 0; i < N; i++) {
	int x1, y1, x2, y2;
	scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
	if(x1>x2)swap(x1, x2);
	if(y1>y2)swap(y1, y2);
	for (size_t i = x1; i <= x2; i++) {
	for (size_t j = y1; j <= y2; j++) {
	arr[i][j] = true;//all occpuied
	}
	}
	}
	int sum=0;
	for (size_t i = 1; i <= W; i++) {
	for (size_t j = 1; j <= H; j++) {
	sum += arr[i][j]==true;
	}
	}
	sum = W*H-sum;
	if(sum==0)
	printf("There is no empty spots.\n");
	else if(sum==1)
	printf("There is one empty spot.\n");
	else
	printf("There are %d empty spots.\n", sum);
	}
	return 0;
	}

Uva 11349 Symmetric Matrix:

Note that int won't work in this case, you should use long long.

Everthing else is just simple, do as it asks. Compare each element with the element at its mirror location. Here goes the code:

int main(int argc, char const *argv[]) {
	long long T;
	scanf("%lld", &T);
	for(long long k=0;k<T;k++){
	char ch;
	long long n;
	cin>>ch>>ch>>n;
	long long arr[n][n];
	bool symmetric=true;
	for (size_t i = 0; i < n; i++) {
	for (size_t j = 0; j < n; j++) {
	scanf("%lld", &arr[i][j]);
	if(arr[i][j]<0)
	symmetric=false;
	}
	}
	for(long long i=0;i<n&&symmetric;i++){
	for (long long j = 0; j <n/2 + 1&&symmetric ; j++) {
	if(arr[i][j]!=arr[n-1-i][n-1-j]){
	symmetric = false;
	break;
	}
	}
	}
	if(symmetric){
	printf("Test #%lld: Symmetric.\n", k+1);
	}else{
	printf("Test #%lld: Non-symmetric.\n", k+1);
	}
	}
	return 0;
	}

Uva 11360: Have Fun with matrices

Nothing complex, do as asked. Here is the source code:

int main(int argc, char const *argv[]) {
	int T;
	scanf("%d", &T);
	int CASE=0;
	while (T--) {
	CASE++;
	int N;
	scanf("%d", &N);
	int arr[N][N];
	for (size_t i = 0; i < N; i++) {
	string s;
	cin>>s;
	for (size_t j = 0; j < N; j++) {
	arr[i][j] = s[j] - '0';
	}
	}
	int M;
	scanf("%d", &M);
	for (size_t i = 0; i < M; i++) {
	string s;
	cin>>s;
	if(s=="row"){
	int a,b;
	scanf("%d %d", &a, &b);
	/////////////perform row operation
	for (size_t i = 0; i < N; i++) {
	swap(arr[a-1][i], arr[b-1][i]);
	}
	}
	if(s=="col"){
	int a,b;
	scanf("%d %d", &a, &b);
	/////////////perform col operation
	for (size_t i = 0; i < N; i++) {
	swap(arr[i][a-1], arr[i][b-1]);
	}
	}
	if(s=="inc"){
	/////////////perform inc operation
	for (size_t i = 0; i < N; i++) {
	for (size_t j = 0; j < N; j++) {
	arr[i][j] = (arr[i][j]+1)%10;
	}
	}
	}
	if(s=="dec"){
	/////////////perform dec operation
	for (size_t i = 0; i < N; i++) {
	for (size_t j = 0; j < N; j++) {
	arr[i][j] = (arr[i][j]-1);
	if(arr[i][j]==-1)
	arr[i][j]=9;
	}
	}
	}
	if(s=="transpose"){
	////////////perform transpose operation
	for (size_t i = 0; i < N; i++)
	for (size_t j = 0; j <= i; j++)
	swap(arr[i][j], arr[j][i]);
	}
	}
	printf("Case #%d\n", CASE);
	for (size_t i = 0; i < N; i++) {
	for (size_t j = 0; j < N; j++)
	printf("%d", arr[i][j]);
	printf("\n");
	}
	printf("\n");
	}
	return 0;
	}