Repository navigation
Expand file tree
/
Copy pathmax_depth.cpp
More file actions
123 lines (102 loc) · 2.55 KB
/
Copy pathmax_depth.cpp
File metadata and controls
123 lines (102 loc) · 2.55 KB
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
117
118
119
120
121
122
123
//KNIGHTS TOUR
#include <bits/stdc++.h>
using namespace std;
bool dfs(vector<vector<int>>& matrix,int n,int row,int col,int k){
matrix[row][col] = k;
if(k == n*n)return true;
int diff[8][2] = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
for(int i=0;i<8;i++){
int dr = row+diff[i][0],dc = col+diff[i][1];
if(dr>=1 && dr<=n && dc>=1 && dc<=n && matrix[dr][dc] == -1){
if(dfs(matrix,n,dr,dc,k+1)){
return true;
}
}
}
matrix[row][col] = -1;
return false;
}
int main(){
int n;cin>>n;
int row,col;cin>>row>>col;
vector<vector<int>> matrix(n+1,vector<int>(n+1,-1));
if(dfs(matrix,n,row,col,1)){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<matrix[i][j]<<(j == n ? "":" ");
}
cout<<endl;
}
}
else{
cout<<"No valid tour"<<endl;
}
return 0;
}
// //SYMMENTRY CHECK
// #include <bits/stdc++.h>
// using namespace std;
// struct Node{
// int val;
// Node*left;
// Node* right;
// Node(int v){
// val = v;
// left = right = nullptr;
// }
// };
// bool ismirror(Node* root1,Node* root2){
// if(root1 == nullptr && root2 == nullptr){
// return true;
// }
// else if(root1 == nullptr || root2 == nullptr){
// return false;
// }
// else if(root1->val != root2->val){
// return false;
// }
// bool first = ismirror(root1->left,root2->right);
// bool second = ismirror(root1->right,root2->left);
// return first && second;
// }
// int main(){
// vector<string> arr;
// string elem;
// while(cin>>elem && elem != "-1"){
// arr.push_back(elem);
// }
// Node* root = new Node(stoi(arr[0]));
// queue<Node*> q;
// q.push(root);
// int i = 1;
// while(!q.empty()){
// Node* curr = q.front();
// q.pop();
// if(i<arr.size() && arr[i] != "null"){
// curr->left = new Node(stoi(arr[i]));
// }
// i++;
// if(i<arr.size() && arr[i]!="null"){
// curr->right = new Node(stoi(arr[i]));
// }
// i++;
// }
// cout<<ismirror(root->left,root->right)<<endl;
// return 0;
// }
// //MAX_DEPTH
// #include <bits/stdc++.h>
// using namespace std;
// int f(){
// int n;cin>>n;
// if(n == -1){
// return 0;
// }
// int left = f();
// int right = f();
// return 1+max(left,right);
// }
// int main(){
// cout<<f()<<endl;
// return 0;
// }