題目來源 https://zerojudge.tw/ShowProblem?problemid=a417
這題關鍵思維就是定義出順時鐘跟逆時鐘兩種走向的向量改變,順時鐘是{0 , 1} , {1 , 0} , {0 , -1} , {-1 , 0} ,逆時鐘是{1 , 0} , {0 , 1} , {-1 , 0} , {0 , -1},再來便是開始填數字,要注意的是每填完一圈,下一圈要填的格子會少一個。
如果有什麼不懂得地方再麻煩私訊或是寄信給我囉。
以下附上程式碼:(這題寫得有點亂)
#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
using namespace std;
int n;
void check(int a[4][2] , vector<vector<int>> v) {
int count = 1;
int x = 0 , y = 0;
v[0][0] = count;
int index = 0 , start = 1;
while(true) {
for(int i = start; i < n; i++) {
//cout <<x;
x += a[index][0];
y += a[index][1];
if(v[x][y] == 0) {
v[x][y] = ++count;
} else {
x = x - a[index][0];
y = y - a[index][1];
break;
}
}
if(count == n*n) break;
if(++index == 4) {//每跑完一圈,則每圈要改變的位置少1(start++)
index = 0;
start++;
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << setw(5) << to_string(v[i][j]);
}
cout << "\n";
}
}
int main()
{
//cin.tie(0) , cin.sync_with_stdio(0);
int t;
int m;
vector<vector<int>> v;
vector<int> s;
int a[4][2] = {{0 , 1} , {1 , 0} , {0 , -1} , {-1 , 0}}; //找出順時針跟逆時針兩種方向
int b[4][2] = {{1 , 0} , {0 , 1} , {-1 , 0} , {0 , -1}};
cin >> t;
while(t--) {
cin >> n >> m;
v.clear();
s.clear();
s.assign(n , 0);
v.assign(n , s);
if(m == 1) {
check(a , v);
} else {
check(b , v);
}
}
return 0;
}
沒有留言:
張貼留言