# 演算法課程題解 - 二維陣列
# TOJ 114
## 題目
https://toj.tfcis.org/oj/pro/114/
給一個 $n \times m$ 的陣列，如果其中有連續三個相同的連續元素在同一行或列上，輸出 Yes ，否則輸出 No
## 解法 By Koios1143
### 想法
分別檢查列以及行是否有相同元素即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main(){
int arr[5][6];
for(int i=0 ; i<5 ; i++){
for(int j=0 ; j<6 ; j++){
cin>>arr[i][j];
}
}
bool find_ans=false;
// row
for(int i=0,cnt=1 ; i<5 ; i++,cnt=1){
for(int j=1 ; j<6 && !find_ans ; j++){
if(arr[i][j] == arr[i][j-1])
cnt++;
else
cnt=1;
if(cnt==3)
find_ans=true;
}
}
// col
for(int j=0,cnt=1 ; j<6 ; j++,cnt=1){
for(int i=1 ; i<5 && !find_ans ; i++){
if(arr[i][j] == arr[i-1][j])
cnt++;
else
cnt=1;
if(cnt==3)
find_ans=true;
}
}
if(find_ans)
cout<<"Yes\n";
else
cout<<"No\n";
return 0;
}
```
### 複雜度分析
總時間複雜度約為 $O(3nm)$
# UVa 10189
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10189
有一個地雷區，寬與長分別為 $n, m$ ，地雷以 `*` 表示
輸出每個非地雷的點四周八個方向總共有多少個地雷
## 解法 By Koios1143
### 想法
對於地圖上的每一個非地雷的點，直接檢查八個方向有多少地雷記錄下來即可
這裡有個小技巧，我們將八個方向 $x$ 和 $y$ 分別改變的大小用陣列記錄下來，接下來當我們要檢查八個方向，就只需要用 for 迴圈跑過一遍就可以了!
另外，這裡使用 cango 來判斷一個點是否超出範圍，在程式碼書寫上會變得更淺顯易懂
### 程式碼
```cpp=
#include<iostream>
using namespace std;
int n,m,Case=1,dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{1,-1},{-1,1},{1,1}};
char arr[105][105];
bool cango(int x,int y){
if(x<0 || x>=n || y<0 || y>=m) return false;
return true;
}
int main(){
bool out=false;
while(cin>>n>>m && (n||m)){
if(out){
cout<<'\n';
}
else{
out=true;
}
cout<<"Field #"<<Case++<<":\n";
// input
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<m ; j++){
cin>>arr[i][j];
}
}
// solve
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<m ; j++){
if(arr[i][j] == '*'){
cout<<'*';
}
else{
int cnt=0;
for(int k=0 ; k<8 ; k++){
// 枚舉八個方向
int nx=i+dir[k][0];
int ny=j+dir[k][1];
// 點在範圍內
if(cango(nx,ny)){
if(arr[nx][ny] == '*'){
cnt++;
}
}
}
cout<<cnt;
}
}
cout<<'\n';
}
}
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度為 $O(nm)$
最差情況對於每個點都要檢查八個方向，複雜度為 $O(8nm)$
單筆測茲的時間複雜度為 $O(9nm)$ 約為 $O(nm)$
# ZJ b266
## 題目
https://zerojudge.tw/ShowProblem?problemid=b266
給一個經過幾個操作的矩陣，求原本矩陣的長寬以及該矩陣
可行的操作包括
- 翻轉
- 旋轉
特別注意到，他要的是原本的矩陣所以所有操作都要反過來做
## 解法 By Koios1143
### 程式碼
```cpp=
#include<iostream>
using namespace std;
int r,c,m,arr[15][15],op[15];
bool out=false;
void rotate(){
int tmp[15][15];
swap(r,c);
for(int i=0 ; i<r ; i++){
for(int j=0 ; j<c ; j++){
tmp[i][j] = arr[j][r-i-1];
}
}
swap(arr,tmp);
}
void mirror(){
int tmp[15][15];
for(int arr_x=r-1, tmp_x=0 ; arr_x>=0 ; arr_x--, tmp_x++){
for(int j=0 ; j<c ; j++){
tmp[tmp_x][j] = arr[arr_x][j];
}
}
swap(arr,tmp);
}
int main(){
while(cin>>r>>c>>m){
if(out){
cout<<"\n";
}
else{
out=true;
}
for(int i=0 ; i<r ; i++){
for(int j=0 ; j<c ; j++){
cin>>arr[i][j];
}
}
for(int i=0 ; i<m ; i++){
cin>>op[i];
}
for(int i=m-1 ; i>=0 ; i--){
if(op[i]==0){
rotate();
}
else{
mirror();
}
}
cout<<r<<" "<<c<<"\n";
for(int i=0 ; i<r ; i++){
for(int j=0 ; j<c ; j++){
if(j) cout<<' ';
cout<<arr[i][j];
}
cout<<"\n";
}
}
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度為 $O(rc+m)$
翻轉與旋轉的時間複雜度皆為 $O(rc)$
每筆測資的時間複雜度為 $O(rc+m+mrc)$ 約為 $O(mrc)$
# UVa 10010
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10010
給一個 $m \times n$ 的圖，每個格子上都有一個字
接下來會有 $k$ 個字串，要問這個字串在圖中的位置，並且保證一定存在
我們在圖中尋找的方向有8個 : 往左、往右、往上、往下、往左上、往左下、往右上、往右下
並且請忽視大小寫
## 解法 By Koios1143
### 想法
對於每個點，如果和詢問的第一個字相同，就以它為起點向8個方向找，如果找到答案就直接輸出
這裡一樣用到 dir 陣列儲存八個方位的 $x, y$ 座標變化量
並且用 cango 判斷是否還在圖的範圍內
### 程式碼
```cpp=
#include<iostream>
using namespace std;
int t,m,n,k,dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
char arr[55][55];
string query;
bool out=false;
bool cango(int x,int y){
// 判斷是否超出範圍
if(x<0 || x>=m || y<0 || y>=n) return false;
return true;
}
bool find_ans(int x, int y, int len){
// 向8個方向找答案，並回傳是否找到答案
for(int i=0 ; i<8 ; i++){
bool end=true;
for(int step=0 ; step<len ; step++){
int nx=x+dir[i][0]*step;
int ny=y+dir[i][1]*step;
if(!cango(nx,ny) || arr[nx][ny]!=query[step]){
// 不能走，或是不匹配則必定非為答案
end=false;
break;
}
}
if(end) return true;
}
return false;
}
int main(){
cin>>t;
while(t--){
if(out){
cout<<"\n";
}
else{
out=true;
}
cin>>m>>n;
for(int i=0 ; i<m ; i++){
for(int j=0 ; j<n ; j++){
cin>>arr[i][j];
arr[i][j]=tolower(arr[i][j]);
}
}
cin>>k;
while(k--){
cin>>query;
for(int i=0 ; i<query.size() ; i++){
query[i]=tolower(query[i]);
}
bool end=false;
int ans_x=-1,ans_y=-1;
for(int i=0 ; i<m ; i++){
for(int j=0 ; j<n && !end ; j++){
if(arr[i][j]==query[0] && find_ans(i,j,query.size())){
cout<<i+1<<" "<<j+1<<"\n";
end=true;
}
}
}
}
}
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度為 $O(mn)$
對於8個方位的查詢，時間複雜度可以估計為 $O(1)$
則查詢的時間複雜度約為 $O(mn)$
總時間複雜度為 $O(tmn)$
# UVa 118
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?118
有幾個機器人在 $x \times y$ 大小的地圖裡移動
移動方式包含 `左轉` `右轉` `前進`
當機器人走出地圖邊界，就會掉下去，並且在最後經過的點坐下標記
當其他機器人下次要走出地圖邊界，並且看到這個標記時，會自動忽略掉下去的指令
現在針對每一個機器人，詢問移動結束後的座標位置
## 解法 By Koios1143
### 想法
直接將整個過程模擬過一遍
記得除了記錄現在在哪裡之外，也要記錄當前面向哪個方向
### 程式碼
```cpp=
#include<iostream>
using namespace std;
int n,m,sx,sy,face,arr[55][55];
char c,dir[4]={'N','E','S','W'};
string op;
int get_face(char ch){
if(ch=='N') return 0;
else if(ch=='E') return 1;
else if(ch=='S') return 2;
return 3;
}
int main(){
cin>>n>>m;
while(cin>>sx>>sy>>c){
// 以數字表示方位
face=get_face(c);
cin>>op;
bool lost=false;
// 針對指令進行操作
for(int i=0 ; i<op.size() ; i++){
if(op[i]=='L'){
face--;
if(face<0) face=3;
}
else if(op[i]=='R'){
face++;
if(face>3) face=0;
}
else{
if(face==0){
if(sy+1>m){
if(arr[sx][sy]==0){
arr[sx][sy]=-1;
lost=true;
break;
}
}
else
sy++;
}
else if(face==1){
if(sx+1>n){
if(arr[sx][sy]==0){
arr[sx][sy]=-1;
lost=true;
break;
}
}
else
sx++;
}
else if(face==2){
if(sy-1<0){
if(arr[sx][sy]==0){
arr[sx][sy]=-1;
lost=true;
break;
}
}
else
sy--;
}
else if(face==3){
if(sx-1<0){
if(arr[sx][sy]==0){
arr[sx][sy]=-1;
lost=true;
break;
}
}
else
sx--;
}
}
}
cout<<sx<<" "<<sy<<" "<<dir[face];
if(lost){
cout<<" LOST\n";
}
else{
cout<<'\n';
}
}
return 0;
}
```
### 時間複雜度分析
對於每一個指令操作的時間複雜度為 $O(1)$
操作每個機器人的時間複雜度為 $O(len(op))$
## 解法 By sa072686
### 想法
建表和餘數都是好東西，人人都該學
### 程式碼
```cpp=
#include<iostream>
using namespace std;
int n,m,sx,sy, nx, ny,face,arr[55][55];
char c;
string dir = "NESW";
int tbl[128];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
string op;
int main(){
int i;
for (i=0; i<dir.size(); i++)
{
tbl[dir[i]] = i;
}
cin>>n>>m;
while(cin>>sx>>sy>>c){
// 以數字表示方位
face=tbl[c];
cin>>op;
bool lost=false;
// 針對每個指令進行操作
for(int i=0 ; i<op.size() ; i++){
if(op[i]=='L'){
face = (face+3) % 4;
}
else if(op[i]=='R'){
face = (face+1) % 4;
}
else{
nx = sx + dx[face];
ny = sy + dy[face];
if (nx < 0 || nx > n || ny < 0 || ny > m)
{
if (arr[sx][sy] == 0)
{
arr[sx][sy] = -1;
lost = true;
break;
}
}
else
{
sx = nx;
sy = ny;
}
}
}
cout<<sx<<" "<<sy<<" "<<dir[face];
if(lost){
cout<<" LOST\n";
}
else{
cout<<'\n';
}
}
return 0;
}
```
### 時間複雜度分析
對於每一個指令操作的時間複雜度為 $O(1)$
操作每個機器人的時間複雜度為 $O(len(op))$
# UVa 10500
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10500
給一張地圖，如果不能走的話會標記 $X$ ，你會從起點 $(x,y)$ 開始走，每次檢查4個方向，並將看到的結果記錄下來
檢查過程當中，依序檢查 北 東 南 西 ，第一次遇到可以走的就走過去
在4個方向都不能走的情況下結束，並輸出紀錄的結果以及走過的步數
## 解法 By Koios1143
### 想法
直接把走的過程模擬過一遍
從起點開始，每次檢查4個方向記錄下來，並且走向第一個可以走的地方
一直重覆到不能走為止，將結果輸出即可
記得方向要從 北->東->南->西
另外，在檢查四個方向的過程中，記得不要往走過的點走，不然可能會永遠不會結束喔w
### 程式碼
```cpp=
#include<iostream>
using namespace std;
int n,m,x,y,dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
char arr[15][15], res[15][15];
bool vis[15][15];
void init(){
// 初始化
for(int i=0 ; i<15 ; i++){
for(int j=0 ; j<15 ; j++){
arr[i][j]='X';
res[i][j]='?';
vis[i][j]=false;
}
}
}
void print_table(){
// 輸出表格的間隔
for(int i=1 ; i<=m ; i++){
cout<<"|---";
}
cout<<"|\n";
}
bool cango(int x, int y){
// 判斷是否在圖的範圍內
if(x<0 || x>n || y<0 || y>m) return false;
return true;
}
int main(){
while(cin>>n>>m && (n||m)){
init();
cin>>x>>y;
for(int i=1 ; i<=n ; i++){
for(int j=1 ; j<=m ; j++){
cin>>arr[i][j];
}
}
res[x][y]='0';
vis[x][y]=true;
int move=0;
while(true){
bool found=false;
int found_x,found_y;
for(int i=0 ; i<4 ; i++){
int nx=x+dir[i][0];
int ny=y+dir[i][1];
res[nx][ny]=arr[nx][ny];
if(cango(nx,ny) && arr[nx][ny]!='X' && !found && !vis[nx][ny]){
found=true;
found_x=nx;
found_y=ny;
vis[found_x][found_y]=true;
}
}
if(found){
x=found_x;
y=found_y;
move++;
}
else{
break;
}
}
cout<<"\n";
for(int i=1 ; i<=n ; i++){
print_table();
for(int j=1 ; j<=m ; j++){
if(j==1) cout<<"|";
cout<<" "<<res[i][j]<<" |";
}
cout<<"\n";
}
print_table();
cout<<"\n";
cout<<"NUMBER OF MOVEMENTS: "<<move<<"\n";
}
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度 $O(nm)$
每次針對4個方向尋找，時間複雜度視為 $O(1)$
最糟的情況需要將棋盤全部遍歷過，時間複雜度為 $O(nm)$
輸出時間複雜度也為 $O(nm)$
每筆測資總時間複雜度為 $O(3nm)$ 約為 $O(nm)$
# UVa 10196
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10196
給一個西洋棋盤的盤面，以小寫表示黑色，大寫表示白色
棋盤包含幾種棋子
- Pawn（士兵，以p或P表示）
- Knight（騎士，以n或N表示)
- Bishop（主教，以b或B表示）
- Rook（城堡，以r或R表示）
- Queen（皇后，以q或Q表示）
- King（國王，以k或K表示）
現在給你一個盤面，求是否有 白色/黑色 的國王正處於可以被攻擊的狀態，或是沒有這兩種狀態
保證沒有兩者同時處在可被攻擊狀態的情況
## 解法 By Koios1143
### 想法
很有趣的實作題w
基本上我們可以直接針對所有在盤面上的棋子都動動看，如果遇到可以攻擊敵方國王就直接輸出
如果寫得很冗長也許是很正常的
在書寫過程中也許會發現到時常出現重複的問題
這時候就可以好好善用 function 的優勢，讓程式碼變得更加簡潔
並且建議在寫這樣的實作題可以直接在 main 完成，並假定某個 function 能具有什麼功能，等到 main 寫完，再去完成那些 function
這樣寫起來會順暢許多
### 程式碼
```cpp=
#include<iostream>
using namespace std;
int game=1;
int pb[2][2]={{1,-1},{1,1}},pw[2][2]={{-1,-1},{-1,1}};
int knight[8][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
char board[10][10];
bool cango(int x,int y){
// 判斷是否超出棋盤
if(x<0 || x>=8 || y<0 || y>=8) return false;
return true;
}
bool rock(int x, int y, int color){
// 判斷城堡是否能 check
char king;
if(color==0)
king='K';
else
king='k';
for(int i=x-1 ; i>=0 ; i--){
//up
if(board[i][y]==king)
return true;
else if(board[i][y]!='.')
break;
}
for(int i=x+1 ; i<8 ; i++){
//down
if(board[i][y]==king)
return true;
else if(board[i][y]!='.')
break;
}
for(int i=y-1 ; i>=0 ; i--){
//left
if(board[x][i]==king)
return true;
else if(board[x][i]!='.')
break;
}
for(int i=y+1 ; i<8 ; i++){
//right
if(board[x][i]==king)
return true;
else if(board[x][i]!='.')
break;
}
return false;
}
bool bishop(int x,int y,int color){
// 判斷主教是否能 check
char king;
if(color==0)
king='K';
else
king='k';
for(int i=x-1, j=y+1 ; i>=0 && j<8 ; i--, j++){
// upper right
if(board[i][j]==king)
return true;
else if(board[i][j]!='.')
break;
}
for(int i=x-1, j=y-1 ; i>=0 && j>=0 ; i--, j--){
// upper left
if(board[i][j]==king)
return true;
else if(board[i][j]!='.')
break;
}
for(int i=x+1, j=y+1 ; i<8 && j<8 ; i++, j++){
// lower right
if(board[i][j]==king)
return true;
else if(board[i][j]!='.')
break;
}
for(int i=x+1, j=y-1 ; i<8 && j>=0 ; i++, j--){
// upper left
if(board[i][j]==king)
return true;
else if(board[i][j]!='.')
break;
}
return false;
}
bool check_over(char chess, int x, int y, int color){
// 確認是否能 check
char ch=tolower(chess);
if(ch=='p'){
// pawn
if(color==0){
// black
for(int i=0 ; i<2 ; i++){
int nx=x+pb[i][0];
int ny=y+pb[i][1];
if(cango(nx,ny) && board[nx][ny]=='K')
return true;
}
}
else{
//white
for(int i=0 ; i<2 ; i++){
int nx=x+pw[i][0];
int ny=y+pw[i][1];
if(cango(nx,ny) && board[nx][ny]=='k')
return true;
}
}
}
else if(ch=='r'){
// rook
return rock(x,y,color);
}
else if(ch=='b'){
// bishop
return bishop(x,y,color);
}
else if(ch=='q'){
// queen
return rock(x,y,color) || bishop(x,y,color);
}
else if(ch=='n'){
// knight
char king;
if(color==0)
king='K';
else
king='k';
for(int i=0 ; i<8 ; i++){
int nx=x+knight[i][0];
int ny=y+knight[i][1];
if(cango(nx,ny) && board[nx][ny]==king)
return true;
}
return false;
}
return false;
}
int main(){
while(true){
bool end=false;
for(int i=0 ; i<8 ; i++){
for(int j=0 ; j<8 ; j++){
cin>>board[i][j];
if(board[i][j]!='.')
end=true;
}
}
if(!end)
break;
bool found=false;
for(int i=0 ; i<8 && !found ; i++){
for(int j=0 ; j<8 && !found ; j++){
if(board[i][j]=='.' || board[i][j]=='k' || board[i][j]=='K')
continue;
if(islower(board[i][j])){
// black
if(check_over(board[i][j], i, j, 0)){
cout<<"Game #"<<game<<": white king is in check.\n";
game++;
found=true;
}
}
else{
// white
if(check_over(board[i][j], i, j, 1)){
cout<<"Game #"<<game<<": black king is in check.\n";
game++;
found=true;
}
}
}
}
if(!found){
cout<<"Game #"<<game<<": no king is in check.\n";
game++;
}
}
return 0;
}
```
### 時間複雜度分析
假設棋盤邊長為 $N$
輸入時間複雜度為 $O(N^2)$
所有棋子針對任意方向的搜尋時間複雜度都視為 $O(1)$
最差情況盤面上每個點都需要搜尋過，時間複雜度為 $O(N^2)$
每筆測資時間複雜度為 $O(2 \times N^2)$ 約為 $O(N^2)$
###### tags: `SCIST 演算法 題解`
Sign in with Wallet
Connect another wallet