---
# System prepended metadata

title: 陣列、地圖、模擬題型
tags: [apcs, 歷屆練習, 陣列模擬, 矩陣運算, 陣列規律, 自主學習, 解題筆記]

---

###### tags: `apcs` `解題筆記` `歷屆練習` `自主學習`
陣列、地圖、模擬題型
===
{%hackmd BJrTq20hE %}
[TOC]

## 陣列
陣列是很好用的解題工具，陣列搭配迴圈、條件判斷可以解很多題型，也很適合拿來儲存各種資料，這周對地圖與模擬類的題型做研究。二維陣列適合矩陣運算與地圖的模擬。二微陣列存四方是最常用的方法
```java=
int[][] direction = {
	{-1,0},
	{0,-1},
	{1,0},
	{0,1}
};
```
## [歷屆:數字龍捲風](https://zerojudge.tw/ShowProblem?problemid=c292)
![](https://i.imgur.com/oFnNQPe.jpg)
用二維陣列跑動四個方向，是模擬地圖很好用的工具
###### tags: `陣列規律`
```java=
import java.io.*;
import static java.lang.System.*;
import static java.lang.Integer.*;
public class p2 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(in));
		int n = parseInt(br.readLine());
		int d = parseInt(br.readLine());
		int[][] numbers = new int[n][n];
		StringBuilder answer = new StringBuilder();
		int times = 0;
		for(int j = 0;j < n;j++) {
			String[] datas = (br.readLine()).split(" ");
			for(int i = 0;i < n;i++)
				numbers[i][j] = parseInt(datas[i]);
		}
		//放入起始中心位置
		int x = (n+1)/2 -1;
		int y = x;
		answer.append(numbers[x][y])  ;
		times++;
		numbers[x][y] = -1;
		//用二維陣列跑四方
		int[][] direction = {
				{-1,0},
				{0,-1},
				{1,0},
				{0,1}
		};
		//跑n*n-1次結束
		int t = n*n-1;
		while(t-->0) {
			//跑過的變-1，判斷決定轉彎
			if(numbers[x+direction[d][0]][y+direction[d][1]] != -1) {
				answer.append(numbers[x+direction[d][0]][y+direction[d][1]]) ;
				times++;
				numbers[x+direction[d][0]][y+direction[d][1]] = -1;
				x += direction[d][0];
				y += direction[d][1];
				d++;
				if(d == 4)
					d = 0;
				if(numbers[x+direction[d][0]][y+direction[d][1]] == -1) {
					if(d == 0)
						d = 3;
					else
						d--;
				}
	
			}
		}
		out.println(answer);
	}
}
```
## [歷屆:機器人的路徑](https://zerojudge.tw/ShowProblem?problemid=e287)
![](https://i.imgur.com/FSSgbMJ.jpg)
###### tags: `陣列模擬`
```java=
import java.io.*;
public class p2{
	public static int n = 0,m = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] d = (br.readLine()).split(" ");
		n = Integer.parseInt(d[0]);
		m = Integer.parseInt(d[1]);
		int x = 0,y = 0,min= 1000000,minx = 0,miny = 0;
		int[][] numbers = new int[m][n];
		for(int i = 0;i < n;i++) {
			d = (br.readLine()).split(" ");
			for(int j = 0;j < m;j++) {
				numbers[j][i] = Integer.parseInt(d[j]);
				if(numbers[j][i] < min) {
					min = numbers[j][i];
					x = j;
					y = i;
				}
			}
		}
		int ans = 0;
		//二維陣列跑四方
		int[][] dir = {
				{1,0},
				{0,1},
				{0,-1},
				{-1,0}
		};
		while(true) {
			min = 1000000;
			for(int i = 0;i < 4;i++) {
				if(inmap(x+dir[i][0],y+dir[i][1])) {
					if(numbers[x+dir[i][0]][y+dir[i][1]] != 0 ) {
						if(numbers[x+dir[i][0]][y+dir[i][1]] <min) {
							min = numbers[x+dir[i][0]][y+dir[i][1]] ;
							minx = x + dir[i][0];
							miny = y + dir[i][1];
						}
					}
				}
			}
			ans += numbers[x][y];
			numbers[x][y] = 0;
			x = minx;
			y = miny;
			if(min == 1000000)
				break;
		}
		System.out.println(ans);
	}
	//判斷是否在地圖裡
	public static boolean inmap (int x,int y) {
		if(x < 0 || x >= m||y < 0 || y >= n) {
			return false;
		}
		return true;
	}

}

```
## [歷屆:矩陣翻轉](https://zerojudge.tw/ShowProblem?problemid=b266)

因為沒有特別需要用Java所以用C++
###### tags: `矩陣運算`
![](https://i.imgur.com/ajs3YCX.jpg)
```cpp=
#include<stdio.h>
int main()
{
    int R=0,C=0,M=0;
    int matrix[10][10]={{0}};
    int operation[10]={0};

    scanf("%d %d %d",&R,&C,&M);

    //獲得陣列
    for(int i=0;i<R;++i)
    {
        for(int j=0;j<C;++j)
        {
            scanf(" %d",&matrix[i][j]);
        }
    }

    //獲得操作
    for(int i=0;i<M;++i)
    {
        scanf(" %d",&operation[i]);
    }

    //反推每個操作
    for(int i=M-1;i>=0;--i)
    {
        //旋轉
        if(operation[i]==0)
        {
            //宣告暫時儲存用矩陣
            int temp_matrix[10][10]={{0}};

            //調整行數和列數
            int temp=C;
            C=R;
            R=temp;

            //進行翻轉
            for(int x=0;x<R;++x)
            {
                for(int y=0;y<C;++y)
                {
                    //(x,y)會移到(y,行數-x-1)
                    temp_matrix[x][y]=matrix[y][R-x-1];
                }
            }

            //將翻轉後的矩陣填回
            for(int x=0;x<R;++x)
            {
                for(int y=0;y<C;++y)
                {
                    matrix[x][y]=temp_matrix[x][y];
                }
            }
        }
        //翻轉
        else
        {
            for(int x=0;x<R/2;++x)
            {
                for(int y=0;y<C;++y)
                {
                    //(x,y)會和(行數-x-1,y)交換
                    int temp=matrix[x][y];
                    matrix[x][y]=matrix[R-x-1][y];
                    matrix[R-x-1][y]=temp;
                }
            }
        }
    }

    //輸出行數和列數
    printf("%d %d",R,C);
    //輸出陣列
    for(int x=0;x<R;++x)
    {
        printf("\n");
        for(int y=0;y<C;++y)
        {
            if(y!=0)printf(" ");
            printf("%d",matrix[x][y]);
        }
    }
    return 0;
}

```
## [歷屆:人口遷移](https://zerojudge.tw/ShowProblem?problemid=f313)
![](https://i.imgur.com/KED5OcN.jpg)
在外維多設一圈-1可以防止超出範圍，把遷移的變數用另一個陣列存起來最後在一次改變
###### tags: `陣列模擬`
```java=
import java.io.*;
public class p2 {

	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//輸入
		String[] d = (br.readLine()).split(" ");
		int r = Integer.parseInt(d[0]);
		int c = Integer.parseInt(d[1]);
		int k = Integer.parseInt(d[2]);
		int m = Integer.parseInt(d[3]);
		//System.out.printf("%d %d\n",r,c );
		int[][] city = new int[r+2][c+2];//城市人口
		int[][] migrate = new int[r+2][c+2];//一次轉移人口
		for(int j = 0;j < r+2;j++) {
			if(j >= 1 && j <= r)
				d = (br.readLine()).split(" ");
			for(int i = 0;i < c+2;i++) {
				if(j == 0 || j == r+1||i == 0||i == c+1) {
					city[j][i] = -1;
				}else {
					city[j][i] = Integer.parseInt(d[i-1]);
				}
				migrate[j][i] = 0;
			}
		}
		//二維陣列跑四方
		int[][] dir = {
				{1,0},
				{0,1},
				{0,-1},
				{-1,0}
			};
		while(m-->0) {
			for(int j =1 ;j < r+1;j++) {
				for(int i = 1;i < c+1;i++) {
					if(city[j][i] != -1) {
						int mi = city[j][i]/k;
						int t = 0;
						for(int q = 0;q < 4;q++) {
							if(city[j+dir[q][0]][i+dir[q][1]]!=-1) {
								migrate[j+dir[q][0]][i+dir[q][1]] += mi;
								t++;
							}
						}
						migrate[j][i] -= t * mi;
					}
				}
			}
			for(int j = 1;j < r+1;j++) {
				for(int i = 1;i < c+1;i++) {
					city[j][i] += migrate[j][i];
				}
			}
			for(int j = 1;j < r+1;j++)
				for(int i = 0;i < c+1;i++)
					migrate[j][i] = 0;
		}
		int big = city[1][1];
		int small = city[1][1];
		for(int j = 1;j < r+1;j++) {
			for(int i = 1;i < c+1;i++) {
				if(city[j][i] != -1) {
					if(city[j][i]>big)
						big = city[j][i];
					if(city[j][i]<small)
						small = city[j][i];
				}
			}
		}
		System.out.printf("%d\n%d\n",small,big);
	}
}

```
## [歷屆:骰子翻轉](https://zerojudge.tw/ShowProblem?problemid=f580)
![](https://i.imgur.com/0VvKtoW.jpg)
判斷六個面，按邏輯判斷翻轉就可以解開。
###### tags: `陣列模擬`
```java=
import java.io.*;
public class p2 {
	public static int top = 1,front = 2,botton = 3,back = 4,right = 6,left = 5;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] d = (br.readLine()).split(" ");
		int n = Integer.parseInt(d[0]);
		int m = Integer.parseInt(d[1]);
		int[][] dice = new int[n+1][7];
		for(int i = 1;i <= n;i++) {
			dice[i][top] = 1;
			dice[i][front] = 4;
			dice[i][botton] = 6;
			dice[i][back] = 3;
			dice[i][left] = 5;
			dice[i][right] = 2;
		}
		for(int i = 0;i < m;i++) {
			d = (br.readLine()).split(" ");
			int a = Integer.parseInt(d[0]);
			int b = Integer.parseInt(d[1]);
			if(b >= 0) {
				int[] temp = new int[6];
				temp = dice[a];
				dice[a] = dice[b];
				dice[b] = temp;
			}else if(b == -1) {
				int temp = dice[a][top];
				dice[a][top] = dice[a][back];
				dice[a][back] = dice[a][botton];
				dice[a][botton] = dice[a][front];
				dice[a][front] = temp;
				//printDice(dice[a]);
			}else {
				int temp = dice[a][top];
				dice[a][top] = dice[a][left];
				dice[a][left] = dice[a][botton];
				dice[a][botton] = dice[a][right];
				dice[a][right] = temp;
				//printDice(dice[a]);
			}
		}
		for(int i = 1;i <= n;i++) {
			if(i != 1)
				System.out.print(" ");
			System.out.print(dice[i][top]);
		}
		System.out.println();
		
	}
	public static void printDice(int[] dice) {
		System.out.printf("\n %d\n%d%d%d%d\n %d\n",dice[back],dice[left],dice[top],dice[right],dice[botton],dice[front]);
	}

}

```
## [歷屆:流量](https://zerojudge.tw/ShowProblem?problemid=f606)
![](https://i.imgur.com/LfIjWhr.jpg)
用二維陣列模擬伺服器對城市，最後再輸出，須注意合併流量的判斷
###### tags: `陣列模擬`
```java=
import java.io.*;

public class p2 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] d = br.readLine().split(" ");
		int n = Integer.parseInt(d[0]);
		int m = Integer.parseInt(d[1]);
		int k = Integer.parseInt(d[2]);
		int[][] q = new int[n][m];
		int[][] f = new int[m][m];
		int ans = 10000000;
		//輸入
		for(int i = 0;i < m;i++)
			for(int j = 0;j < m;j++)
				f[i][j] = 0;
		for(int j = 0;j < n;j++) {
			d = br.readLine().split(" ");
			for(int i = 0;i < m;i++){
				q[j][i] = Integer.parseInt(d[i]);
			}
		}
		while(k --> 0) {
			int fee = 0;
			int[] seat = new int[n];
			d = br.readLine().split(" ");
			for(int i = 0;i < n;i++)
				seat[i] = Integer.parseInt(d[i]);
			for(int i = 0;i < n;i++) {
				for(int j = 0;j < m;j++) {
					f[seat[i]][j] += q[i][j];
				}
			}
			
			for(int i = 0;i < m;i++) {
				for(int j = 0;j < m;j++) {
					if(i == j)
						fee += f[i][j];
					else
						fee += (f[i][j] <= 1000 ? f[i][j]*3 : f[i][j]*2 + 1000);
					f[i][j] = 0;
				}
			}
			if(fee<ans)
				ans = fee;
		}
		System.out.println(ans);
	}

}

```
## [歷屆:魔王迷宮](https://zerojudge.tw/ShowProblem?problemid=g276)
![](https://i.imgur.com/GhPU92H.jpg)
利用陣列與條件判斷，容易漏掉條件而出小錯誤(考的時候就漏掉一個條件而沒拿到分..)
###### tags: `陣列模擬`
```java=
import static java.lang.System.*;
import static java.lang.Integer.*;
import java.io.*;
public class zj_g276 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(in));
		String[] d = br.readLine().split(" ");
		int nn = parseInt(d[0]);
		int m = parseInt(d[1]);
		int kk = parseInt(d[2]);
		int[][] n = new int[nn][m];
		int[][] k = new int[kk][5];
		for(int i = 0;i < kk;i++) {
			d = br.readLine().split(" ");
			int r = parseInt(d[0]);
			int c = parseInt(d[1]);
			int s = parseInt(d[2]);
			int t = parseInt(d[3]);
			k[i][0] = r;
			k[i][1] = c;
			k[i][2] = s;
			k[i][3] = t;
			k[i][4] = 1;
			n[r][c] = 1;
		}
		int x = 0;
		while(true) {
			boolean has = false;
			for(int i = 0;i < kk;i++) {
				if(k[i][4]!=0) {
					has = true;
					k[i][0] += k[i][2];
					k[i][1] += k[i][3];
					if(k[i][0]<0||k[i][1]<0||k[i][0]>=nn||k[i][1]>=m) {
						k[i][4] = 0;
					}
					else if(n[k[i][0]][k[i][1]] == 1||n[k[i][0]][k[i][1]] ==2) {
						n[k[i][0]][k[i][1]] = 2;
						k[i][4] = 0;
					}
					else if(n[k[i][0]][k[i][1]] ==0) {
						n[k[i][0]][k[i][1]] =3;
					}
				}
			}
			for(int i = 0;i < nn;i++) {
				for(int j = 0;j < m;j++) {
					if(n[i][j] == 2) {
						n[i][j] = 0;
					}
					if(n[i][j] == 3) {
						n[i][j] = 1;
					}
				}
			}
			if(!has)
				break;
		}
		int ans = 0;
		for(int i = 0;i < nn;i++) {
			for(int j = 0;j < m;j++) {
				if(n[i][j] ==1) {
					ans++;
				}
			}
		}
		out.println(ans);

	}

}

```

