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;
}