###### tags: `apcs` `解題筆記` `歷屆練習` `自主學習`
陣列、地圖、模擬題型
===
{%hackmd BJrTq20hE %}
[TOC]
## 陣列
陣列是很好用的解題工具，陣列搭配迴圈、條件判斷可以解很多題型，也很適合拿來儲存各種資料，這周對地圖與模擬類的題型做研究。二維陣列適合矩陣運算與地圖的模擬。二微陣列存四方是最常用的方法
```java=
int[][] direction = {
{-1,0},
{0,-1},
{1,0},
{0,1}
};
```
## [歷屆:數字龍捲風](https://zerojudge.tw/ShowProblem?problemid=c292)
用二維陣列跑動四個方向，是模擬地圖很好用的工具
###### 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)
###### 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: `矩陣運算`
```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)
在外維多設一圈-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)
判斷六個面，按邏輯判斷翻轉就可以解開。
###### 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)
用二維陣列模擬伺服器對城市，最後再輸出，須注意合併流量的判斷
###### 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)
利用陣列與條件判斷，容易漏掉條件而出小錯誤(考的時候就漏掉一個條件而沒拿到分..)
###### 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);
}
}
```
Sign in with Wallet
Connect another wallet