【題目鏈接】

ybt 1967：【14NOIP普及組】螺旋矩陣
洛谷 P2239 [NOIP2014 普及組] 螺旋矩陣

類似考題：
洛谷 P1014 [NOIP1999 普及組] Cantor 表

【題目考點】

1.二維數(shù)組

【解題思路】

記輸入的目標(biāo)位置為(ai, aj)
如果暴力移動焦點，在二位數(shù)組中蛇形填寫數(shù)字，因為數(shù)組邊長達(dá)到30000，數(shù)組元素個數(shù)為$30000?30000=9?10^8$，默認(rèn)計算機1s可以進(jìn)行小于$10^8$次運算，這樣做一定會超時。
每圈的元素個數(shù)是容易求的，如果每次移動一圈，到(ai，aj)所在的圈時再一個一個格子移動，這樣移動次數(shù)就會大大減少。
第1圈邊長為n，元素個數(shù)為4*(n-1)
第2圈邊長為n-2，元素個數(shù)為4*(n-2-1)
…
第i圈邊長為n-2*(i-1)，元素個數(shù)為4*(n-2*(i-1)-1)
每圈邊長比上一圈少2，元素個數(shù)為4*(邊長-1)

第i圈:上面一行的行坐標(biāo)為：i，下面一行行坐標(biāo)為：n-i+1，左側(cè)一列列坐標(biāo)為：i，右側(cè)一列列坐標(biāo)為n-i+1。
如果目標(biāo)位置：(ai, aj)的行坐標(biāo)ai為i或n-i+1，或列坐標(biāo)aj為i或n-i+1，說明(ai,aj)在第i圈。然后可以有兩種方法確定(ai, aj)位置的值。

解法1：移動焦點

第i圈邊長為l=n-2*(i-1)，將一圈分為等長的四部分，每部分長度為:l-1。焦點從左上角出發(fā)，向右移動l-1次后，焦點指向右上角；再向下移動l-1次后，焦點指向右下角；再向左移動l-1次，焦點指向左下角；再向上移動l-1次，完成對第i圈的遍歷。
在這一過程中，記錄到每個位置時數(shù)組元素值。如果遍歷到(ai, aj)，輸出該值。

解法2：坐標(biāo)計算

記第i圈左上角位置(i,i)的值為st，邊長為l。那么右上角(i,n-i+1)的值為：st+l-1，右下角(n-i+1,n-i+1)的值：st+(l-1)*2，左下角(n-i+1,i)的值：st+(l-1)*3。

• 如果目標(biāo)位置在第i行，需要從左上角(i,i)移動到(ai,aj)位置，移動aj-i次，值需要加aj-i，那么(ai,aj)位置的值為st+aj-i
• 如果目標(biāo)位置在第n-i+1列，需要從右上角(i,n-i+1)移動到(ai,aj)位置，移動ai-i次，那么(ai,aj)位置的值為st+(l-1)+ai-i
• 如果目標(biāo)位置在第n-i+1行，需要從右下角(n-i+1,n-i+1)移動到(ai,aj)位置，移動n-i+1-aj次，那么(ai,aj)位置的值為st+2*(l-1)+(n+1-i)-aj
• 如果目標(biāo)位置在第i列，需要從左下角(n-i+1,i)移動到(ai,aj)位置，移動n-i+1-ai次，那么(ai,aj)位置的值為st+3*(l-1)+(n+1-i)-ai

【題解代碼】

解法1：移動焦點

#include<bits/stdc++.h> using namespace std; int main() {int n, ai, aj, i, st, l;//求(ai,aj)的數(shù) st:該圈起始數(shù)字 int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};//右下左上 cin >> n >> ai >> aj;st = 1, l = n;//st:起始數(shù)字， l:該圈邊長 for(i = 1; i <= n/2; ++i){//看ai，aj是否在第i圈 if(ai == i || ai == n+1-i || aj == i || aj == n+1-i)break;st += 4*l-4;l -= 2; }//看ai,aj位置是第i圈上第幾個格子，求出目標(biāo)位置的值 int fi = i, fj = i, num = st;//fi,fj:焦點 num:該位置的值 for(int d = 0; d < 4; ++d)//方向 0:右 1:下 2:左 3:上 {int k = 1;do//用do...while是為了當(dāng)l==1時，也會判斷輸出解。解決找邊長為奇數(shù)的二維數(shù)組中心位置的問題。 {if(fi == ai && fj == aj)//找到目標(biāo)位置 {cout << num;return 0;}fi += dir[d][0], fj += dir[d][1];//按照d方向移動到下一個位置 num++;k++;}while(k <= l-1);//每一條邊遍歷l-1次 }return 0; }

解法2：坐標(biāo)計算

#include<bits/stdc++.h> using namespace std; int main() {int n, ai, aj, i, st, l;//求(ai,aj)的數(shù) st:該圈起始數(shù)字 cin >> n >> ai >> aj;st = 1, l = n;//st:起始數(shù)字， l:該圈邊長 for(i = 1; i <= n/2; ++i){//看ai，aj是否在第i層外圈 if(ai == i || ai == n+1-i || aj == i || aj == n+1-i)break;st += 4*l-4;l -= 2; }if(ai == i)//在第i行cout << st+aj-i;//移動aj-i次else if(aj == n+1-i)//在第n-i+1列cout << st+l-1+ai-i;//移動ai-i次else if(ai == n+1-i)//在第n-i+1行cout << st+2*(l-1)+(n+1-i)-aj;//移動(n+1-i)-aj次else if(aj == i)//在第i列cout << st+3*(l-1)+(n+1-i)-ai;//移動(n+1-i)-ai次return 0; }

解法3：遞歸

#include<bits/stdc++.h> using namespace std; int getNum(int l, int i, int j)//左上角(1,1)位置的值為1，邊長為l的矩陣中(i,j)的值 {if(i == 1)//如果在上邊 return j;else if(j == l)//如果在右邊 return l-1+i;else if(i == l)//如果在下邊 return 2*(l-1)+l-j+1;else if(j == 1)//如果在左邊 return 3*(l-1)+l-i+1;else//如果在內(nèi)部 i，j位置的值為這一圈元素的個數(shù)（4*(l-1)）加上以(2,2)位置為左上角，以l-2長度為邊的矩陣中，(i-1,j-1)位置的值。 return 4*(l-1)+getNum(l-2, i-1, j-1);//以(2,2)位置為左上角時， 原(2,2)變?yōu)?1,1)，原(i,j)變?yōu)?i-1,j-1) } int main() {int n, ai, aj;//求(ai,aj)的數(shù) st:該圈起始數(shù)字 cin >> n >> ai >> aj;cout << getNum(n, ai, aj);return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 1967：【14NOIP普及组】螺旋矩阵 | 洛谷 P2239 [NOIP2014 普及组] 螺旋矩阵的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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