【題目鏈接】

ybt 2045：【例5.13】蛇形填數(shù)

【題目考點(diǎn)】

1. 二維數(shù)組

2. 方向數(shù)組（可能用到）

int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
d為當(dāng)前方向，0:下，1：左，2：上， 3：右
dir[d]為按d方向移動(dòng)后橫縱坐標(biāo)的變化量，即位置(x,y)按d方向移動(dòng)到的下一個(gè)位置為(x+dir[d][0], y+dir[d][1])

【解題思路】

方法1：移動(dòng)焦點(diǎn)位置

設(shè)二維數(shù)組，每個(gè)位置初值為0。設(shè)置關(guān)注的焦點(diǎn)位置(fx, fy)，初始值為1，所在的位置(1, n)。用一個(gè)變量表示當(dāng)前焦點(diǎn)移動(dòng)方向，初值為向下。
首先將焦點(diǎn)位置賦值為1，焦點(diǎn)按照當(dāng)前移動(dòng)方向移動(dòng)一次，然后將新的位置賦值為2，然后重復(fù)進(jìn)行移動(dòng)、賦值操作。如果移出二維數(shù)組范圍，或移動(dòng)后焦點(diǎn)的位置已經(jīng)有值了（不為0），那么就改變移動(dòng)方向。移動(dòng)方向按照下、左，上，右的順序循環(huán)變化。
可以用一個(gè)整數(shù)d表示方向，0：下 1：左 2：上 3：右。若想變?yōu)橄乱粋€(gè)方向，只需運(yùn)行：d = (d + 1) % 4 即可。
該方法可以通過判斷當(dāng)前方向做不同操作，或使用方向數(shù)組實(shí)現(xiàn)

方法2：按圈賦值

以圈為單位，從外向內(nèi)進(jìn)行遍歷、賦值。

• 第1圈遍歷過程為：(1,n)向下到(n,n)，(n, n-1)向左到(n, 1)， (n-1, 1)向上到(1,1)， (1,2)向右到(1, n-1)
• 第2圈遍歷過程為：(2,n-1)向下到(n-1,n-1)，(n-1, n-2)向左到(n-1, 2)， (n-2, 2)向上到(2,2)， (2,3)向右到(2, n-2)
  …
• 根據(jù)規(guī)律，第i圈遍歷過程為：(i, n-i+1)向下到(n-i+1,n-i+1)，(n-i+1, n-i)向左到(n-i+1, i)， (n-i, i)向上到(i,i)， (i,i+1)向右到(i, n-i)
• n為1時(shí)有1圈，n為2時(shí)有1圈，n為3時(shí)有2圈，n為4時(shí)有2圈…一共有$?\frac{n}{2}?$圈

【題解代碼】

解法1：移動(dòng)焦點(diǎn)位置

• 使用判斷語句判斷當(dāng)前移動(dòng)方向

#include<bits/stdc++.h> using namespace std; int main() {int a[25][25] = {}, n, fx, fy;//數(shù)組a各元素初值為0， fx,fy為焦點(diǎn)位置 int dir = 0;//表示方向 0:下 1：左 2：上 3：右cin >> n;//二維數(shù)組寬度 fx = 1, fy = n; //起始焦點(diǎn)位置(1, n) for(int i = 1; i <= n*n; ++i)//一共n*n個(gè)格子 {//數(shù)字i的位置是fx，fy a[fx][fy] = i;switch(dir)//判斷移動(dòng)方向{case 0://下fx++;//焦點(diǎn)向下移動(dòng) if(fx == n || a[fx+1][fy] != 0)//如果已經(jīng)到了第n行，或下一次要到的位置已經(jīng)有值了 dir = (dir + 1) % 4;//移動(dòng)方向變?yōu)橄乱粋€(gè)方向 break;case 1://左fy--;if(fy == 1 || a[fx][fy-1] != 0)dir = (dir + 1) % 4;break;case 2://上fx--;if(fx == 1 || a[fx-1][fy] != 0)dir = (dir + 1) % 4;break;case 3://右fy++;if(fy == n || a[fx][fy+1] != 0)dir = (dir + 1) % 4;break;}}for(int i = 1; i <= n; ++i)//輸出二維數(shù)組 {for(int j = 1; j <= n; ++j)cout << a[i][j] << ' ';cout << endl;}return 0; }

• 使用方向數(shù)組

#include<bits/stdc++.h> using namespace std; int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};//方向數(shù)組 int main() {int a[25][25] = {}, k = 1, n, fx, fy, d = 0, x, y;//fx, fy當(dāng)前焦點(diǎn)位置 x,y下一個(gè)位置 d:方向 cin >> n;fx = 1, fy = n;while(k <= n*n){a[fx][fy] = k++; // 賦值 x = fx + dir[d][0], y = fy + dir[d][1]; //下一個(gè)位置 if(a[x][y] != 0 || x > n || x < 1 || y > n || y < 1)//如果新位置上已經(jīng)有值了或移出了二維數(shù)組范圍d = (d + 1) % 4;//變換方向 fx += dir[d][0], fy += dir[d][1];//更新焦點(diǎn)位置 }for(int i = 1; i <= n; ++i){for(int j = 1; j <= n; ++j)cout << a[i][j] << ' ';cout << endl;}return 0; }

解法2：按圈賦值

#include <bits/stdc++.h> using namespace std; int main() {int a[25][25], n, cnum, x, y, k = 1;cin >> n;cnum = ceil((double)n/2);//共有cnum圈 n為1，2時(shí)要遍歷1圈，n為3，4時(shí)要遍歷2圈。。。 ceil:向上取整 for(int i = 1; i <= cnum; i++)//第i圈 {for(x = i, y = n-i+1; x <= n-i+1; x++)//右上到右下 a[x][y] = k++; for(x = n-i+1, y = n-i; y >= i; y--)//右下到左下 a[x][y] = k++; for(x = n-i, y = i; x >= i; x--)//左下到左上 a[x][y] = k++; for(x = i, y = i+1; y <= n-i; y++)//左上到右上 a[x][y] = k++; }for(int i = 1; i <= n; i++)//輸出 {for(int j = 1; j <= n; j++)cout << a[i][j] << ' ';cout << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 2045：【例5.13】蛇形填数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。