C++

Forum

 
Populating matrix diagonally from cordinates

Firedragon123 (3)
Hello,

here is the example of inputs and outputs.

input: 
1
2
3
4
5
6
7
 
6 10 R
..........
..........
..........
..P.......
..........
..........


where 6 means how many rows are in the matrix, 10 is how many columns are in the matrix, and R is in which direction should the matrix be filled in from the P cordinates.

Example of output:
1
2
3
4
5
6
 
........xx
......xxxx
....xxxxxx
..Pxxxxxxx
....xxxxxx
......xxxx




if there are any "O" in the matrix then the "x" after and diagonally to "P" should be filled with the "."
Here is an example:

Input:
1
2
3
4
5
6
7
 
6 10 R
..........
.......O..
..........
..P..O....
..........
..........

Output:
1
2
3
4
5
6
 
........x.
......xO..
....xxx...
..PxxO....
....xxx...
......xxx.


Also here are more of examples for other directions.
Left example:
Input:
1
2
3
4
5
6
7
8
9
10
11
 
10 20 L
....................
....................
....................
................P...
....................
....O...............
....................
....................
....................
....................

Output:
1
2
3
4
5
6
7
8
9
10
 
xxxxxxxxxxx.........
xxxxxxxxxxxxx.......
xxxxxxxxxxxxxxx.....
xxxxxxxxxxxxxxxxP...
xxxxxxxxxxxxxxx.....
....Oxxxxxxxx.......
...xxxxxxxx.........
.xxxxxxxx...........
xxxxxxx.............
xxxxx...............


Dircetion UP:
input:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
43 31 U
..O.......O....................
..................O............
.....O.........................
........................OO.....
...............................
...............................
...............................
.....O.........................
...............................
...............................
...............................
.....................O.........
...............................
...............................
...............................
...............................
.O.............................
...............O...............
...............................
................O..............
...............................
...............................
................O..............
............P..................
...............................
...............................
...............................
...............................
.....OO.....O...........OO.....
............O..................
............O..................
............O..................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................

Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
.xO...xxxxOxxxx................
.x....xxxxxxxxx...O............
..x..Oxxxxxxxxx................
..x...xxxxxxxxx.........OO.....
...x..xxxxxxxxx................
...x..xxxxxxxxx................
....x.xxxxxxxxx................
....xOxxxxxxxxx................
.....xxxxxxxxxx................
.....xxxxxxxxxx................
......xxxxxxxxx................
......xxxxxxxxx......O.........
.......xxxxxxxx................
.......xxxxxxxx................
........xxxxxxx................
........xxxxxxx................
.O.......xxxxxx................
.........xxxxxxO...............
..........xxxxx................
..........xxxxx.O..............
...........xxx.................
...........xxx.................
............x...O..............
............P..................
...............................
...............................
...............................
...............................
.....OO.....O...........OO.....
............O..................
............O..................
............O..................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................


Down direction:
input:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
43 31 D
..O.......O....................
..................O............
.....O.........................
........................OO.....
...............................
...............................
...............................
.....O......................P..
...............................
...............................
...............................
.....................O.........
...............................
...............................
...............................
...............................
.O.............................
...............O...............
...............................
................O..............
...............................
...............................
................O..............
...............................
...............................
...............................
...............................
...............................
.....OO.....O...........OO.....
............O..................
............O..................
............O..................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................

Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
..O.......O....................
..................O............
.....O.........................
........................OO.....
...............................
...............................
...............................
.....O......................P..
............................x..
...........................xxx.
...........................xxx.
.....................O....xxxxx
..........................xxxxx
.........................xxxxxx
.........................xxxxxx
........................xxxxxxx
.O......................xxxxxxx
...............O.......xxxxxxxx
.......................xxxxxxxx
................O.....xxxxxxxxx
......................xxxxxxxxx
.....................xxxxxxxxxx
................O....xxxxxxxxxx
....................xxxxxxxxxxx
....................xxxxxxxxxxx
...................xxxxxxxxxxxx
...................xxxxxxxxxxxx
..................xxxxxxxxxxxxx
.....OO.....O.....xxxxxxOOxxxxx
............O....xxxxxxx..xxxxx
............O....xxxxxx...xxxxx
............O...xxxxxxx...xxxxx
................xxxxxx....xxxxx
...............xxxxxxx....xxxxx
...............xxxxxx.....xxxxx
..............xxxxxxx.....xxxxx
..............xxxxxx......xxxxx
.............xxxxxxx......xxxxx
.............xxxxxx.......xxxxx
............xxxxxxx.......xxxxx
............xxxxxx........xxxxx
...........xxxxxxx........xxxxx
...........xxxxxx.........xxxxx
salem c (3700)
And your question is?

No, this isn't a site where you can dump your assignment on us and expect a complete answer you can run back to teacher with.
Firedragon123 (3)
The question is how to implement such algorithm. I have done this so far:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#define MAX_S 100
#define MAX_R 100


void unos(char mat[][MAX_S], int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf(" %c", &mat[i][j]);
		}
	}

}

void ispis(char* mat, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			printf("%c", *(mat + i * MAX_S + j));
		}
		printf("\n");
	}


}
void popunjavanje(char* pMat, int n, int  m, int korI, int korJ, int smjer) {
	
	if (smjer == 'R') {
		for (int i = 0; i < n; i++) {
			for (int j = korJ + 1; j < m; j++) {

				if ((i + j) == (n)) {
					//*(pMat + i * MAX_S + j) = 'x';
					for (int r = j; r < m; r++) { /// popunjavane reda u kojem se nalazi dijagonalni x
						*(pMat + i * MAX_S + r) = 'x';
					}
				}
				if (i == j) {
					//*(pMat + i * MAX_S + j) = 'x';
					for (int r = j; r < m; r++) { /// popunjavane reda u kojem se nalazi dijagonalni x
						*(pMat + i * MAX_S + r) = 'x';
					}
				}
			}
		}
	}

	if (smjer == 'L') {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < korJ - 1; j++) {
				//*(pMat + i * MAX_S + j) = 'x';
				

				if ((i + j) == (n)) {
					*(pMat + i * MAX_S + j) = 'x';
					//for (int r = j; r >= 0; r--) { /// popunjavane reda u kojem se nalazi dijagonalni x
						//*(pMat + i * MAX_S + r) = 'x';
					//}
				}
				if (i == j) {
					*(pMat + i * MAX_S + j) = 'x';
					//for (int r = j; r >= 0; r--) { /// popunjavane reda u kojem se nalazi dijagonalni x
						//*(pMat + i * MAX_S + r) = 'x';
					//}
				}
				

			}
		}
	}
	
	
	// 1, zadaj kordinate.
	// 2. ako je desno, od j koridnate popunjavaj desno, za redak koridinate x. 
	// 3. sljedeci red je korJ+1 i KorI+1, odn 
	
	//for (int i = 0; i < n; i++) {
	//	for (int j = 0; j < m; j++) {
	//		if (*(pMat + i * MAX_S + j) == 'P') {
	//			// printf("naso p na lokaciji %d %d", i, j);
	//			
	//		
	//		
	//		}
	//	}
	//}

}


int main() {
	char mat[MAX_R][MAX_S] = { '0' };
	int n, m, korI = 0, korJ = 0;
	char smjer;
	scanf("%d %d %c", &n, &m, &smjer);
	unos(mat, n, m);
	// ispis(&mat[0][0], n, m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (mat[i][j] == 'P') {
				korI = i;
				korJ = j;
			}
		}
	}
	printf("%d %d\n", korI, korJ);
	popunjavanje(&mat[0][0], n, m,korI, korJ, smjer);
	printf("\n");
	ispis(&mat[0][0], n, m);
	// for j
	


	return 0;
}


The function "popunjavanje" is the one that should fill in the x-s.
jonnin (11443)
Building the algorithm depends on what the rules are, first.
It looks like there are 4 directions up/down/left/right. If you need to do 365 (1 for each degree angle in a circle, for example) then a 4 way branch is horrible. If you know you only ever want 4 of the, then a 4 way branch is "OK" at least as a starting point -- so find P, and if 'U' fill in loop else if 'D' different fill in loop ... or you can have a flexible fill in function and call it with 4 parameter sets based off the input.

so start there: if it will only be the 4 directions, can you fill in from P in the desired direction, ignoring O for now?
Once you can do that, then you also want to fill in the O part. It looks to be similar to P, but only 1/2 the cone (??) or is it trig based (??). Ideally you can find a way to fill in P and not do anything in the O spots, that is, only do the P work if there is no blocking O work, for maximum efficiency but that assumes it was . to begin with, and you don't need to flip back because an O was added later (??). If you have to flip them, then still skip those Ps but fill in the Os too.

Break it down, test as you do each part.
It looks like you are doing much of what I said -- what is not working for you?
Last edited on
Firedragon123 (3)
Can you write down the algorithm for the first test case? Because im kinda strugling right now to write it..
1
2
3
4
5
6
7
8
 
void popunjavanje(char* pMat, int n, int  m, int korI, int korJ, int smjer) {
	
	if (smjer == 'R') {
        //algorithm for populating x for right side. Without O’s

}
		
	}
jonnin (11443)
if P is at (R,C) (row, column)

something like this. you need to add bounds checking so you do not exceed the rows on this sample. 
1
2
3
4
5
6
7
8
 
for(int r = 0, int c = C+1; c < num_columns; c++)
{
     for(int i = R-r; i<= R+r; i++)
       image[i][c] = 'x';
r++;
}
Last edited on
salem c (3700)
Here's an idea that might help you to think about directions just being a dx/dy instead of 4 blocks of near identical code dealing with each direction as a special case.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
#include <iostream>
#include <string>
#include <vector>
#include <limits>
#include <sstream>
using namespace std;

using vs = vector<string>;

enum direction_t { UP, LEFT, DOWN, RIGHT };

direction_t getCode(char ch) {
  if ( ch == 'U' ) return UP;
  if ( ch == 'L' ) return LEFT;
  if ( ch == 'D' ) return DOWN;
  if ( ch == 'R' ) return RIGHT;
}

// Fill a row from a point to one end of the line or the other.
void fill_row(vs &map, int row, int col, int col_direction) {
  if ( row < 0 || row > map.size() ) return;
  int c = col + col_direction;
  while ( c >= 0 && c < map[row].size() ) {
    map[row][c] = 'X';
    c += col_direction;
  }
}

// Fan out a triangle of X from the given start position.
void filler(vs &map, int row, int col, direction_t direction_code ) {
  static struct {
    int delta_r;
    int delta_c;
  } position_offsets[] = {
    { -1, 0 },  // up
    { 0, -1 },  // left
    { +1, 0 },  // down
    { 0, +1 },  // right
  };

  if ( row < 0 || row > map.size() ) return;

  if ( position_offsets[direction_code].delta_r == 0 ) {
    fill_row(map, row, col, position_offsets[direction_code].delta_c);
    // either side
    for ( int i = 1 ; i < 3 ; i++ ) {
      fill_row(map, row-i, col, position_offsets[direction_code].delta_c);
      fill_row(map, row+i, col, position_offsets[direction_code].delta_c);
      col += position_offsets[direction_code].delta_c;
    }
  } else {
    // you do up/down
  }
}

void fill_from(vs &map, direction_t direction_code, char where) {
  for ( size_t r = 0 ; r < map.size() ; r++ ) {
    size_t c = map[r].find(where);
    if ( c != string::npos ) {
      filler(map,r,c,direction_code);
    }
  }
}

void read_input(vs &map, direction_t &direction_code) {
  int n_rows, n_cols;
  string direction;
  cin >> n_rows >> n_cols >> direction;
  cin.ignore(numeric_limits<streamsize>::max(), '\n');
  direction_code = getCode(direction[0]);
  for ( int r = 0 ; r < n_rows ; r++ ) {
    string line;
    getline(cin,line);
    if( line.length() != n_cols ) {
      cout << "Not a row:" << line << endl;
    } else {
      map.push_back(line);
    }
  }
}

int main ( ) {
  direction_t direction_code;
  vs map;
  read_input(map, direction_code);
  fill_from(map, direction_code, 'P');
  for ( auto &&s : map ) {
    cout << s << endl;
  }
}



$ g++ -g -std=c++11 foo.cpp
$ ./a.out < foo.txt 
..........
....XXXXXX
...XXXXXXX
..PXXXXXXX
...XXXXXXX
....XXXXXX
$ ./a.out < data.txt 
....................
XXXXXXXXXXXXXXX.....
XXXXXXXXXXXXXXXX....
XXXXXXXXXXXXXXXXP...
XXXXXXXXXXXXXXXX....
XXXXXXXXXXXXXXX.....
....................
....................
....................
....................
Topic archived. No new replies allowed.