NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2007高中組初賽
 NPSC 2007 高中組 初賽 A.千里傳情

作者 主題: NPSC 2007 高中組 初賽 A.千里傳情  (閱讀 1819 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 225
    • 檢視個人資料
NPSC 2007 高中組 初賽 A.千里傳情
« 於: 十二月 04, 2009, 09:54:00 am »

NPSC 2007 高中組 初賽 A.千里傳情

說明:給你一個大寫字母和空格組成的字串,依照空格為0、A為1、B為2、...、Z為26的規則,將它們轉換成五位數的二進位數字,再順時針方向放入一個 R*C 的字元陣列中,印出這陣列最後的樣子。

解法:直解或摸擬題,用一個變數 d 紀錄目前的方向,當碰到邊界時則改變方向,並調整邊界值,請特別注意 R=1 或 C=1 的情況。另外,可以將 0 ~ 26 的二進位的字串事先以表格方式儲存,加快處理速度。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2007 初賽 - 題目 A - 千里傳情 //
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int MAX=20, NUM1=27, NUM2=5;
char table[NUM1][NUM2], ans[MAX][MAX];
// 陣列 table 記錄這 27 個字母的二進位字串, 陣列 ans 記錄結果

// 建立 0 ~ 26 的二進位字串對應表
void Init()
{
    const int bit=0x0010; // 00010000
    int i, j;
    for (i=0; i<NUM1; i++)
        for (j=0; j<NUM2; j++)
            table[i][j] = ( ( i & (bit>>j) ) ? '1' : '0' );
}

// 進行編碼
void Encrypt(char s[], int r, int c)
{
    int i, j, x1=0, x2=c-1, y1=1, y2=r-1, d= ( c==1 ? 1 : 0),
        x=0, y=0, a, l=strlen(s);
    // x1, x2, y1, y2 為上下左右的邊界值, d 為前進方向

    // 全部歸零
    for (i=0; i<r; i++)
        for (j=0; j<c; j++)
            ans[i][j]='0';
    for (i=0; i<l; i++)
    {
        a = ( s[i]==' ' ? 0 : s[i]-64 );
        // 填入 s[i] 的二進位字串
        for (j=0; j<NUM2; j++)
        {
            ans[y][x]=table[a][j];
            // 移到下一個位置
            switch (d)
            {
                case 0: // 向右
                    if ( ++x==x2 ) d=1, x2--;
                    break;
                case 1: // 向下
                    if ( ++y==y2 ) d=2, y2--;
                    break;
                case 2: // 向左
                    if ( --x==x1 ) d=3, x1++;
                    break;
                case 3: // 向上
                    if ( --y==y1 ) d=0, y1++;
                    break;
            }
        }
    }
}

int main()
{
    ifstream fin("pa.in");
    ofstream fout("pa.out");
    int k, serial, r, c, i, j;
    char s[MAX*MAX], t;

    Init();
    fin >> k;
    for (serial=1; serial<=k; serial++)
    {
        fin >> r >> c;
        fin.get(t); // 讀取空格
        fin.getline(s, MAX*MAX);
        Encrypt(s, r, c);
        // 列印結果
        fout << serial << " ";
        for (i=0; i<r; i++)
            for (j=0; j<c; j++)
                fout << ans[i][j];
        fout << endl;
    }

//    system("PAUSE");
    return 0;
}
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2007高中組初賽
 NPSC 2007 高中組 初賽 A.千里傳情