ITSA線上程式競賽題目-中文題庫
=======================
## 2048
```cpp=
#include<iostream>
#include<sstream>
using namespace std;
int main(){
char v;
while(cin>>v){
cin.ignore(1,'\n');
string s;
long a[4][4];
for(int i=0;i<4;i++)
{
getline(cin,s);
istringstream ss(s);
string cut;
for(int j=0;j<4;j++){
getline(ss,cut,' ');
istringstream cc(cut);
cc>>a[i][j];
}
}
if(v=='U')
{for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
for(int i=k+1;i<4;i++){
if(a[k][j]!=0&&a[i][j]!=0&&a[k][j]==a[i][j]){
a[k][j]+=a[i][j];
a[i][j]=0;
break;
}
else if(a[k][j]!=0&&a[i][j]!=0&&a[k][j]!=a[i][j]){break;}
for(int i=k+1;i<4;i++){
if(a[k][j]==0&&a[i][j]!=0){
a[k][j]+=a[i][j];
a[i][j]=0;
break;
}}
}
}
}}
else if(v=='D')
{for(int j=0;j<4;j++){
for(int k=3;k>0;k--){
for(int i=k-1;i>=0;i--){
if(a[k][j]!=0&&a[i][j]!=0&&a[k][j]==a[i][j]){
a[k][j]+=a[i][j];
a[i][j]=0;
break;
}
else if(a[k][j]!=0&&a[i][j]!=0&&a[k][j]!=a[i][j]){break;}
for(int i=k-1;i>=0;i--){
if(a[k][j]==0&&a[i][j]!=0){
a[k][j]+=a[i][j];
a[i][j]=0;
break;
}}
}
}
}}
else if(v=='L')
{for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
for(int i=k+1;i<4;i++){
if(a[j][k]!=0&&a[j][i]!=0&&a[j][k]==a[j][i]){
a[j][k]+=a[j][i];
a[j][i]=0;
break;
}
else if(a[j][k]!=0&&a[j][i]!=0&&a[j][k]!=a[j][i]){break;}
for(int i=k+1;i<4;i++){
if(a[j][k]==0&&a[j][i]!=0){
a[j][k]+=a[j][i];
a[j][i]=0;
break;
}}
}
}
}}
else if(v=='R')
{for(int j=0;j<4;j++){
for(int k=3;k>0;k--){
for(int i=k-1;i>=0;i--){
if(a[j][k]!=0&&a[j][i]!=0&&a[j][k]==a[j][i]){
a[j][k]+=a[j][i];
a[j][i]=0;
break;
}
else if(a[j][k]!=0&&a[j][i]!=0&&a[j][k]!=a[j][i]){break;}
for(int i=k-1;i>=0;i--){
if(a[j][k]==0&&a[j][i]!=0){
a[j][k]+=a[j][i];
a[j][i]=0;
break;
}}
}
}
}}
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(j==3){cout<<a[i][j];}
else{cout<<a[i][j]<<" ";}
}cout<<endl;
}
}
return 0;
}
```
## 迷宮問題
```cpp=
//右下角為出發點 (8,8) ，左上角為出口 (1,1)
//右 > 上 > 左 > 下
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
using namespace std;
void p(vector<vector<string> >& map) //印出二維向量
{
for(int i=0;i<10;i++)
{
for(int j=0;j<10;j++)
{
if(j<9)cout<<map[i][j]<<" "; //要留意為什麼是 j，易錯點
else cout<<map[i][j]<<endl;
}
}
}
bool dfs( vector<vector<string> >& map,int sr/*上下*/,int sc/*左右*/)
{//右下角為出發點 (8,8) ，左上角為出口 (1,1)
if( sr > 0 && sc > 0 && sr < 9 && sc < 9 )//是否超界
{
if( map[sr][sc] == "0" ){//是否為未探索路徑
map[sr][sc] = "G";//預設為正確路徑
if( dfs( map, sr, sc+1 ) ){//右
return true;
}
else if( dfs( map, sr-1, sc ) ){//上
return true;
}
else if( dfs( map, sr, sc-1 ) ){//左
return true;
}
else if( dfs( map, sr+1, sc ) ){//下
return true;
}
else{
if( sr == 1 && sc == 1 ){//若為終點則改成 X ，且回傳正確
map[sr][sc] = "X";
return true;
}
else{//否則回傳錯誤並標記為錯誤路徑
map[sr][sc] = "D";
return false;
}
}
}
else return false;//若為已探索則回傳錯誤
}
else return false;//超界回傳錯誤
}
int main()
{
string s;
vector<vector<string> > map;
for(int i=0;i<10;i++) //讀入二維向量
{
getline(cin,s);
vector<string> tmp; //宣告內部向量 tmp
istringstream chs(s); //轉換為可分割字串型態
for(int j=0;j<10;j++)
{
string cs; //宣告被切割的字串 cs
getline(chs,cs,' '); //以空白做切割
tmp.push_back(cs); //存入內部向量 tmp
}
map.push_back(tmp); //再推入外部向量 map
}
dfs(map,8,8);
if( map[1][1] != "X" ){//若終點未被修改則表示未找到
map[1][1] = "X";//標記終點
cout<<"NO"<<endl;
}
else{
cout<<"YES"<<endl;
}
map[8][8] = "S";//標記起點
p(map); //印出二維向量
return 0;
}
```
## C++陣列除法
```cpp=
#include<iostream>
#include<vector>
using namespace std;
int main(){
string str;//讀入字串暫存，
vector<int> a;//被除數
vector<int> b;//除數
bool aORb=true;//判定字串往何處儲存
for(int i=0;i<2;i++)
{
getline(cin,str);//讀入字串
for(int j=0;j<str.size();j++)//與該字串的每個字
{
int changeNum=int(str[j]-'0');//轉成數字
if(aORb==false)//判定是否為除數的字串
{
b.push_back(changeNum);//推入除數字串
}
else
{
a.push_back(changeNum);//推入被除數字串
}
}
aORb=false;//改變下一個字串的儲存區
}
//--------------輸入--------------
vector<int> re;//商
int deltaLen=a.size()-b.size()+1;//計算次數(商數的長度)
int buf[b.size()]={0};//除數計算區初始化
int *ap=&a[0];// 當前計算位置指標
for(int i=0;i<deltaLen;i++)//尋找商數
{
for(int j=0;j<9;j++)//尋找該次商數
{
bool r=false;//判定是否為商數
for(int k=0;k<b.size();k++)//比較大小
{
if(buf[k]<*(ap+k)){break;}//找到任意較小的位數就淘汰
else if(buf[k]>*(ap+k)){r=true;break;}//否則就"錄取"
}
if(r==true)//若為商數，則輸出商數結果
{
re.push_back(j-1);//推入商數結果
for(int m=0;m<b.size();m++)//計算區減一次
{
buf[m]-=b[m];
if(buf[m]<0){buf[m-1]--;buf[m]+=10;}//進位
}
break;//跳出迴圈
}
for(int m=0;m<b.size();m++)//計算區加一次
{
buf[m]+=b[m];
if(buf[m]>10){buf[m-1]++;buf[m]-=10;}//進位
}
}
//--------------找到該次商數--------------
for(int j=0;j<b.size();j++)//與被除數做計算
{
*ap=*ap-buf[j];//減法
if(*ap<0)//進位
{
*(ap-1)-=1;
*ap+=10;
}
ap++;//指標右移
}
ap=ap-(b.size()-1);//指標位置來到下一次計算起始位置
for(int j=0;j<b.size();j++){buf[j]=0;}//計算區歸0
//--------------與被除數計算完畢--------------
}
cout<<"商數為:";
for(int i=0;i<re.size();i++){cout<<re[i];}cout<<endl;
int z=0;//判定首個非0數
b.clear();//淨空再利用，儲存餘數
for(int i=0;i<a.size();i++)//過濾出餘數
{
if(a[i]!=0&&z==0){b.push_back(a[i]);z++;}//遇到首個非0
else if(z!=0){b.push_back(a[i]);}//之後一律推入
}
cout<<"餘數為:";
for(int i=0;i<b.size();i++){cout<<b[i];}cout<<endl;
return 0;
}
```
# 泛洪演算法範例題 --- ITSA- Arrayc 151~200-[C_AR154-易]感染被包圍的人
題目連結：https://e-tutor.itsa.org.tw/eTutor/mod/programming/view.php?id=24871
作法:
```cpp=
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
using namespace std;
void p(vector<vector<string> >& map) //印出二維向量
{
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
if(j<6)cout<<map[i][j]<<" ";
//要留意為什麼是 j，易錯點
else cout<<map[i][j]<<endl;
}
}
}
//銜接下面演算法任一種寫法
```
## 泛洪演算法(一)
```cpp=
//泛洪演算法(一)
void floodfill(vector<vector<string> >& map,int sr,int sc)
{
if(sr >= 0 && sc >= 0 && sr < 7 && sc < 7 && map[sr][sc] == "0")
{ //若沒超出邊界且等於 0
map[sr][sc] = "2"; //將確定生存的目標做標記為2
floodfill(map,sr+1,sc); //上
//floodfill(map,sr+1,sc+1); //右上
floodfill(map,sr,sc+1); //右
//floodfill(map,sr-1,sc+1); //右下
floodfill(map,sr-1,sc); //下
//floodfill(map,sr-1,sc-1); //左下
floodfill(map,sr,sc-1); //左
//floodfill(map,sr+1,sc-1); //左上
}
}
```
## 泛洪演算法(二)
```cpp=
//泛洪演算法(二)
void floodfill(vector<vector<char> >& map, int x, int y)
{
if (x >= 7 || y >= 7 || x < 0 || y < 0)
return;
if (map[x][y] == '0')
{
map[x][y] = '2';
floodfill(map, x - 1, y); //下
//floodfill(map, x - 1, y - 1);//左下
floodfill(map, x, y - 1); //左
//floodfill(map, x + 1, y - 1);//左上
floodfill(map, x + 1, y); //上
//floodfill(map, x + 1, y + 1);//右上
floodfill(map, x, y + 1); //右
//floodfill(map, x - 1, y + 1);//右下
}
if(map[x][y] == 'X' || map[x][y] == '2')
return;
}
```
---銜接前面---
```cpp=
void change(vector<vector<string> >& map,string s,string cs)
{ //將整個二維向量符合 s 的字串替換成字串 cs
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
if(map[i][j]==s)map[i][j]=cs;
}
}
}
int main()
{
string s;
vector<vector<string> > map;
for(int i=0;i<7;i++) //讀入二維向量
{
getline(cin,s);
vector<string> tmp; //宣告內部向量 tmp
istringstream chs(s); //轉換為可分割字串型態
for(int j=0;j<7;j++)
{
string cs; //宣告被切割的字串 cs
getline(chs,cs,' '); //以空白做切割
tmp.push_back(cs); //存入內部向量 tmp
}
map.push_back(tmp); //再推入外部向量 map
}
//僅檢測最外圈是否有 0
//上面的邊
for(int i=0;i<7;i++){if(map[0][i]=="0")floodfill(map,0,i);}
//右邊
for(int i=0;i<7;i++){if(map[i][6]=="0")floodfill(map,i,6);}
//最下排
for(int i=0;i<7;i++){if(map[6][i]=="0")floodfill(map,6,i);}
//最左邊
for(int i=0;i<7;i++){if(map[i][0]=="0")floodfill(map,i,0);}
change(map,"0","I"); //將剩餘的 0，即被感染的替換成 I
change(map,"2","0"); //將標記的 2，替換成 0
p(map); //印出二維向量
return 0;
}
//泛洪演算法範例題 結束
```
Sign in with Wallet
Connect another wallet