青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

雁過無痕
  C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::

問題

1 按順時(shí)針方向構(gòu)建一個(gè)m * n的螺旋矩陣（或按順時(shí)針方向螺旋訪問一個(gè)m * n的矩陣）：

2 在不構(gòu)造螺旋矩陣的情況下，給定坐標(biāo)i、j值求其對(duì)應(yīng)的值f(i, j)。

比如對(duì)11 * 7矩陣， f(6, 0) = 27  f(6, 1) = 52 f(6, 3) = 76  f(6, 4) = 63

 

 

構(gòu)建螺旋矩陣

對(duì)m * n 矩陣，最先訪問最外層的m * n的矩形上的元素，接著再訪問里面一層的 (m - 2) * (n - 2) 矩形上的元素…… 最后可能會(huì)剩下一些元素，組成一個(gè)點(diǎn)或一條線（見圖1）。

對(duì)第i個(gè)矩形（i=0, 1, 2 …），4個(gè)頂點(diǎn)的坐標(biāo)為：

(i, i) ----------------------------------------- (i, n–1-i)

|                                                    |

|                                                    |

|                                                    |

(m-1-i, i) ----------------------------------------- (m-1-i, n-1-i) 

要訪問該矩形上的所有元素，只須用4個(gè)for循環(huán)，每個(gè)循環(huán)訪問一個(gè)點(diǎn)和一邊條邊上的元素即可（見圖1）。另外，要注意對(duì)最終可能剩下的1 * k 或 k * 1矩陣再做個(gè)特殊處理。

 

代碼：

inline void act(int t) { printf("%3d ", t); }

 

 const int small = col < row ? col : row;

 const int count = small / 2;

 for (int i = 0; i < count; ++i) {

    const int C = col - 1 - i;

    const int R = row - 1 - i;

    for (int j = i; j < C; ++j) act(arr[i][j]);

    for (int j = i; j < R; ++j) act(arr[j][C]);

    for (int j = C; j > i; --j) act(arr[R][j]);

    for (int j = R; j > i; --j) act(arr[j][i]);

 }

 

 if (small & 1) {

    const int i = count;

    if (row <= col) for (int j = i; j < col - i; ++j) act(arr[i][j]);

    else for (int j = i; j < row - i; ++j) act(arr[j][i]);

}

 

如果只是構(gòu)建螺旋矩陣的話，稍微修改可以實(shí)現(xiàn)4個(gè)for循環(huán)獨(dú)立：

 

 const int small = col < row ? col : row;

 const int count = small / 2;

 for (int i = 0; i < count; ++i) {

    const int C = col - 1 - i;

    const int R = row - 1 - i;

    const int cc = C - i;

    const int rr = R - i;

    const int s = 2 * i * (row + col - 2 * i) + 1;

    for (int j = i, k = s; j < C; ++j) arr[i][j] = k++;

    for (int j = i, k = s + cc; j < R; ++j) arr[j][C] = k++;

    for (int j = C, k = s + cc + rr; j > i; --j) arr[R][j] = k++;

    for (int j = R, k = s + cc * 2 + rr; j > i; --j) arr[j][i] = k++;

 }

 

 if (small & 1) {

    const int i = count;

    int k = 2 * i * (row + col - 2 * i) + 1;

    if (row <= col) for (int j = i; j < col - i; ++j) arr[i][j] = k++;

    else for (int j = i; j < row - i; ++j) arr[j][i] = k++;

 }

 

關(guān)于s的初始值取 2 * i * (row + col - 2 * i) + 1請(qǐng)參考下一節(jié)。

 

由于C++的二維數(shù)組是通過一維數(shù)組實(shí)現(xiàn)的。二維數(shù)組的實(shí)現(xiàn)一般有下面三種：

靜態(tài)分配足夠大的數(shù)組；

動(dòng)態(tài)分配一個(gè)長為m*n的一維數(shù)組；

動(dòng)態(tài)分配m個(gè)長為n的一維數(shù)組，并將它們的指針存在一個(gè)長為m的一維數(shù)組。

二維數(shù)組的不同實(shí)現(xiàn)方法，對(duì)函數(shù)接口有很大影響。

 

 

 

 

給定坐標(biāo)直接求值f(x, y)

 

如前面所述，對(duì)第i個(gè)矩形（i=0, 1, 2 …），4個(gè)頂點(diǎn)的坐標(biāo)為：

(i, i) ----------------------------------------- (i, n–1-i)

|                                                    |

|                                                    |

|                                                    |

(m-1-i, i) ----------------------------------------- (m-1-i, n-1-i) 

對(duì)給定的坐標(biāo)(x,y)，如果它落在某個(gè)這類矩形上，顯然其所在的矩形編號(hào)為：

k = min{x, y, m-1-x, n-1-y}

m*n矩陣刪除訪問第k個(gè)矩形前所訪問的所有元素后，可得到(m-2*k)*(n-2*k)矩陣，因此已訪問的元素個(gè)數(shù)為：m*n-(m-2*k)*(n-2*k)=2*k*(m+n-2*k)，因而 (k,k)對(duì)應(yīng)的值為：

T(k) = 2*k*(m+n-2*k)+ 1

 

對(duì)某個(gè)矩形，設(shè)點(diǎn)(x, y)到起始點(diǎn)(k,k)的距離d = x-k + y-k = x+y-2*k

① 向右和向下都只是橫坐標(biāo)或縱坐標(biāo)增加1，這兩條邊上的點(diǎn)滿足f(x, y) = T(k) + d

② 向左和向下都只是橫坐標(biāo)或縱坐標(biāo)減少1，這兩條邊上的點(diǎn)滿足f(x, y) = T(k+1) - d

 

如果給定坐標(biāo)的點(diǎn)(x, y)，不在任何矩形上，則它在一條線上，仍滿足f(x, y) = T(k) + d

 

int getv(int row, int col, int max_row, int max_col) // row < max_row, col < max_col

{

 int level = min(min(row, max_row - 1 - row), min(col, max_col - 1 - col));

 int distance = row + col - level * 2;

 int start_value = 2 * level * (max_row + max_col - 2 * level) + 1;

 if (row == level || col == max_col - 1 - level ||

(max_col < max_row && level * 2 + 1 == max_col))

   return start_value + distance;

 int next_value = start_value + (max_row + max_col - 4 * level - 2) * 2;

 return next_value - distance;

}

 

特別說明

上面的討論都是基于m*n矩陣的，對(duì)于特例n*n矩陣，可以做更多的優(yōu)化。比如構(gòu)建螺旋矩陣，如果n為奇數(shù)，則矩陣可以拆分為幾個(gè)矩形加上一個(gè)點(diǎn)。前面的條件判斷可以優(yōu)化為：

if (small & 1) act[count][count];

甚至可以調(diào)整4個(gè)for循環(huán)的遍歷元素個(gè)數(shù)（前面代碼，每個(gè)for循環(huán)遍歷n-1-2*i個(gè)元素，可以調(diào)整為：n-2*i，n-1-2*i, n-1-2*i,n-2-2*i）從而達(dá)到省略if判斷。

 

 

 

測試代碼

代碼1：

 

//螺旋矩陣，給定坐標(biāo)直接求值 by flyinghearts

//www.cnblogs.com/flyinghearts

#include<iostream>

#include<algorithm>

using std::min;

using std::cout;

 

/*

int getv2(int row, int col, int max_row, int max_col) // row < max_row, col < max_col

{

 int level = min(min(row, max_row - 1 - row), min(col, max_col - 1 - col));

 int distance = row + col - level * 2;

 int start_value = 2 * level * (max_row + max_col - 2 * level) + 1;

 if (row == level || col == max_col - 1 - level) return start_value + distance;

 //++level; int next_value = 2 * level * (max_row + max_col - 2 * level) + 1;

 int next_value = start_value + (max_row + max_col - 4 * level - 2) * 2;

 if (next_value > max_col * max_row) return start_value + distance;

 return next_value - distance;

}

*/

 

int getv(int row, int col, int max_row, int max_col) // row < max_row, col < max_col

{

 int level = min(min(row, max_row - 1 - row), min(col, max_col - 1 - col));

 int distance = row + col - level * 2;

 int start_value = 2 * level * (max_row + max_col - 2 * level) + 1;

 if (row == level || col == max_col - 1 - level || (max_col < max_row && level * 2 + 1 == max_col))

    return start_value + distance;

 //++level; int next_value = 2 * level * (max_row + max_col - 2 * level) + 1;

 int next_value = start_value + (max_row + max_col - 4 * level - 2) * 2;

 return next_value - distance;

}

 

 

int main()

{

 

 int test[][2] = {{5, 5}, {5, 7}, {7, 5}, {4, 4}, {4, 6}, {6, 4}};

 const int sz = sizeof(test) / sizeof(test[0]);

 for (int k = 0; k < sz; ++k) {

    int M = test[k][0];

    int N = test[k][1];  

    for (int i = 0; i < M; ++i) {

      for (int j = 0; j < N; ++j)

        cout.width(4), cout << getv(i, j, M, N) << " ";

     cout << "\n"; 

    }

    cout << "\n";

 }

}

 

 

 

 

代碼2：

//螺旋矩陣 by flyinghearts#qq.com

//www.cnblogs.com/flyinghearts

#include<iostream>

 

 

int counter = 0;

 

inline void act(int& t)

{

 //std::cout.width(3), std::cout << t;

 t = ++::counter;

}

 

void act_arr(int *arr, int row, int col, int max_col) //col < max_col

{

 const int small = col < row ? col : row;

 const int count = small / 2;

 int *p = arr;

 for (int i = 0; i < count; ++i) {

    const int C = col - 1 - 2 * i;

    const int R = row - 1 - 2 * i;

    for (int j = 0; j < C; ++j) act(*p++);

    for (int j = 0; j < R; ++j) act(*p), p += max_col;

    for (int j = 0; j < C; ++j) act(*p--);

    for (int j = 0; j < R; ++j) act(*p), p -= max_col;

    p += max_col + 1;

 }

 

 if (small & 1) {

    const int i = count;

    if (row <= col) for (int j = 0; j < col - 2 * i; ++j) act(*p++);

    else for (int j = 0; j < row - 2 * i; ++j) act(*p), p += max_col;

 }

}

 

 

void act_arr(int* arr[], int row, int col)

{

 const int small = col < row ? col : row;

 const int count = small / 2;

 for (int i = 0; i < count; ++i) {

    const int C = col - 1 - i;

    const int R = row - 1 - i;

    for (int j = i; j < C; ++j) act(arr[i][j]);

    for (int j = i; j < R; ++j) act(arr[j][C]);

    for (int j = C; j > i; --j) act(arr[R][j]);

    for (int j = R; j > i; --j) act(arr[j][i]);

 }

 

 if (small & 1) {

    const int i = count;

    if (row <= col) for (int j = i; j < col - i; ++j) act(arr[i][j]);

    else for (int j = i; j < row - i; ++j) act(arr[j][i]);

 }

}

 

void act_arr_2(int* arr[], int row, int col)

{

 const int small = col < row ? col : row;

 const int count = small / 2;

 for (int i = 0; i < count; ++i) {

    const int C = col - 1 - i;

    const int R = row - 1 - i;

    const int cc = C - i;

    const int rr = R - i;

    const int s = 2 * i * (row + col - 2 * i) + 1;

    for (int j = i, k = s; j < C; ++j) arr[i][j] = k++;

    for (int j = i, k = s + cc; j < R; ++j) arr[j][C] = k++;

    for (int j = C, k = s + cc + rr; j > i; --j) arr[R][j] = k++;

    for (int j = R, k = s + cc * 2 + rr; j > i; --j) arr[j][i] = k++;

 }

 

 if (small & 1) {

    const int i = count;

    int k = 2 * i * (row + col - 2 * i) + 1;

    if (row <= col) for (int j = i; j < col - i; ++j) arr[i][j] = k++;

    else for (int j = i; j < row - i; ++j) arr[j][i] = k++;

 }

}

 

void print_arr(int *arr, int row, int col, int max_col) //col < max_col

{

 for (int i = 0, *q = arr; i < row; ++i, q += max_col) {

    for (int *p = q; p < q + col; ++p)

     std::cout.width(4), std::cout << *p;

    std::cout << "\n";

 }

 std::cout << "\n";

}

 

void print_arr(int* a[], int row, int col) //col < max_col

{

 for (int i = 0; i < row; ++i) {

    for (int j = 0; j < col; ++j)

     std::cout.width(4), std::cout << a[i][j];

    std::cout << "\n"; 

 }  

 std::cout << "\n";

}

 

 

void test_1()

{

 const int M = 25;

 const int N = 25;

 int a[M][N];

 int test[][2] = {{5, 5}, {5, 7}, {7, 5}, {4, 4}, {4, 6}, {6, 4}};

 const int sz = sizeof(test) / sizeof(test[0]);

 std::cout << "Test 1:\n";

 for (int i = 0; i < sz; ++i) {

    int row = test[i][0];

    int col = test[i][1];

    if (row < 0 || row > M) row = 3;

    if (col < 0 || col > N) col = 3;

    ::counter = 0;

    act_arr(&a[0][0], row, col, N);

    print_arr(&a[0][0], row, col, N);

 }

}

 

void test_2()

{

 int test[][2] = {{5, 5}, {5, 7}, {7, 5}, {4, 4}, {4, 6}, {6, 4}};

 const int sz = sizeof(test) / sizeof(test[0]);

 std::cout << "Test 2:\n";

 for (int i = 0; i < sz; ++i) {

    int row = test[i][0]; 

    int col = test[i][1]; 

    int **arr = new int*[row];

    for (int i = 0; i < row; ++i) arr[i] = new int[col];

    ::counter = 0;

    act_arr(arr, row, col);

    print_arr(arr, row, col);

    for (int i = 0; i < row; ++i) delete[] arr[i];

    delete[] arr; 

 }

}

 

 

int main()

{

 test_1();

 test_2();

}

 

posted on 2010-12-23 23:09 flyinghearts 閱讀(4999) 評(píng)論(3)  編輯 收藏 引用 所屬分類: 算法

評(píng)論

# re: 螺旋矩陣 2010-12-24 10:10 _飛寒
寒~ 這不是我們學(xué)校的賽題么。。  回復(fù)  更多評(píng)論
  

# re: 螺旋矩陣 2010-12-25 11:20 flyinghearts
@_飛寒
那真湊巧  回復(fù)  更多評(píng)論
  

# re: 螺旋矩陣 2014-08-12 13:57 121e1212
int test[][2] = {{5, 5}, {5, 7}, {7, 5}, {4, 4}, {4, 6}, {6, 4}};

const int sz = sizeof(test) / sizeof(test[0]);

std::cout << "Test 2:\n";

for (int i = 0; i < sz; ++i) {

int row = test[i][0];

int col = test[i][1];

int **arr = new int*[row];

for (int i = 0; i < row; ++i) arr[i] = new int[col];
  回復(fù)  更多評(píng)論
  

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            
欧美欧美在线|
亚洲精品国产品国语在线app|
欧美在线免费一级片|
伊人蜜桃色噜噜激情综合|
欧美成人免费播放|
欧美欧美天天天天操|
午夜视频一区在线观看|
欧美中文字幕视频在线观看|
亚洲国产成人一区|
亚洲精品字幕|
国产日产亚洲精品系列|
欧美成人在线网站|
欧美日韩视频在线一区二区观看视频
|
亚洲电影免费在线观看|
亚洲欧洲精品成人久久奇米网|
国产精品久久久久aaaa九色|
久久久人成影片一区二区三区|
欧美**字幕|
亚洲欧美日韩成人高清在线一区|
欧美专区日韩视频|
一本色道**综合亚洲精品蜜桃冫|
亚洲欧美在线一区二区|
亚洲国产欧美另类丝袜|
亚洲天堂男人|
在线观看中文字幕不卡|
一区二区三区久久久|
极品裸体白嫩激情啪啪国产精品|
亚洲精品乱码久久久久|
国产日韩欧美黄色|
亚洲国产精品免费|
国产欧美一区二区三区在线看蜜臀
|
欧美日韩视频|
久久久水蜜桃|
欧美日韩中文字幕在线|
久久综合伊人|
国产精品久久|
亚洲国产精品久久久久婷婷老年
|
欧美大色视频|
国产精品无人区|
亚洲国产欧美不卡在线观看|
国产精品亚洲а∨天堂免在线|
欧美黑人多人双交|
国产伦精品一区二区三区|
亚洲电影免费观看高清完整版在线观看
|
欧美精品1区|
久久综合中文色婷婷|
国产精品扒开腿爽爽爽视频|
欧美成人免费观看|
国产视频一区在线|
亚洲每日在线|
亚洲国产婷婷|
欧美诱惑福利视频|
中文精品一区二区三区|
久久综合影音|
久久久精品五月天|
国产精品卡一卡二卡三|
亚洲国产毛片完整版|
国产一区二区三区无遮挡|
99在线精品观看|
亚洲三级电影在线观看|
久久久久久高潮国产精品视|
欧美亚洲专区|
欧美三级在线视频|
亚洲国产成人av好男人在线观看|
国精产品99永久一区一区|
亚洲一区二区视频在线|
一本久道久久综合婷婷鲸鱼|
老牛影视一区二区三区|
久久免费黄色|
国产色综合天天综合网|
亚洲性线免费观看视频成熟|
一区二区毛片|
欧美激情亚洲自拍|
欧美黄免费看|
在线免费高清一区二区三区|
欧美主播一区二区三区美女 久久精品人|
亚洲欧美日本另类|
欧美日韩亚洲一区二区三区四区
|
日韩视频中文|
亚洲精品国产系列|
另类酷文…触手系列精品集v1小说|
久久激情视频免费观看|
国产精品自拍在线|
亚洲网站视频福利|
亚洲视频一区二区在线观看|
欧美精品三区|
亚洲精品久久久久久久久久久|
亚洲另类春色国产|
欧美高清一区二区|
亚洲激情成人|
亚洲美女视频|
欧美日韩成人网|
亚洲理伦在线|
亚洲私人黄色宅男|
欧美午夜一区|
亚洲天堂网站在线观看视频|
亚洲中无吗在线|
国产精品美女在线|
亚洲欧美日本在线|
欧美影院久久久|
国产日韩欧美在线|
久久成人国产|
免费亚洲婷婷|
亚洲日本理论电影|
欧美精品麻豆|
一二三区精品福利视频|
亚洲一区二区综合|
国产精品视频精品|
性欧美video另类hd性玩具|
欧美综合国产精品久久丁香|
国产午夜精品久久久久久免费视|
性久久久久久久久久久久|
久久久久久亚洲精品杨幂换脸|
黄色成人小视频|
久久蜜臀精品av|
亚洲成人在线免费|
欧美国产日本在线|
亚洲精品一二|
亚洲专区欧美专区|
国产欧美日韩亚州综合|
欧美中文在线视频|
蜜臀久久99精品久久久画质超高清|
136国产福利精品导航网址应用|
美国成人直播|
亚洲美女淫视频|
欧美一级一区|
狠狠色综合网站久久久久久久|
久热精品在线|
亚洲免费成人|
欧美一区二区在线免费播放|
黄网站免费久久|
欧美韩日一区|
亚洲性av在线|
久久综合色一综合色88|
亚洲人妖在线|
国产精品乱子乱xxxx|
欧美在线影院在线视频|
欧美激情久久久久|
亚洲天堂av高清|
国产一区二区三区自拍|
欧美超级免费视 在线|
亚洲最新在线视频|
久久久久久尹人网香蕉|
亚洲精品久久久久久久久|
欧美午夜不卡视频|
欧美在线日韩在线|
亚洲激情中文1区|
欧美一区日韩一区|
亚洲欧洲日本在线|
国产精品久久午夜夜伦鲁鲁|
久久久久国色av免费看影院|
亚洲精品视频二区|
久久精品中文字幕一区|
亚洲另类自拍|
国产日韩一级二级三级|
欧美成年人视频网站|
亚洲天堂成人在线观看|
蜜桃久久精品一区二区|
亚洲特级片在线|
影音先锋另类|
国产精品成人v|
久久综合网络一区二区|
中文在线资源观看网站视频免费不卡|
狂野欧美性猛交xxxx巴西|
亚洲视频一区在线|
在线日韩成人|
国产精品日韩精品欧美在线
|
欧美国产视频日韩|
欧美一级欧美一级在线播放|
亚洲激情成人在线|
国产日韩欧美亚洲一区|
欧美国产免费|
久久精品30|
一区二区三区成人|
欧美大片一区二区|
欧美在线网站|
亚洲一二三区在线观看|
亚洲第一级黄色片|
国产欧美日韩一区二区三区在线|
欧美国产欧美亚洲国产日韩mv天天看完整|
午夜精品一区二区三区电影天堂
|
欧美国产在线电影|
久久国产欧美|
亚洲一级二级|
亚洲看片免费|
亚洲第一精品久久忘忧草社区|
国产精品免费在线|
欧美极品欧美精品欧美视频|
久久久国际精品|
亚洲自拍16p|
亚洲另类自拍|
欧美激情一区二区三区在线视频观看|
性欧美大战久久久久久久久|
夜夜嗨av一区二区三区网页|
在线观看国产日韩|
国产资源精品在线观看|
国产精品日韩久久久久|
欧美日韩亚洲网|
欧美精品三级在线观看|
裸体丰满少妇做受久久99精品|