ITSA線上程式競賽題目-中文題庫
=======================
## 2048

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

## 迷宮問題

//右下角為出發點 (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++陣列除法

#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

作法:

#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;  
     }  
    }  
} 
//銜接下面演算法任一種寫法

## 泛洪演算法(一)

//泛洪演算法(一)
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); //左上 
   }  
} 

## 泛洪演算法(二)

//泛洪演算法(二)
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;
}

---銜接前面---

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;  
} 
//泛洪演算法範例題 結束