稀疏矩陣設值與查詢

題目敘述

某張成績表有上百欄，但大多數格子都是空的。老師只想記下有填分數的格子，需要時再查某一格的分數。請你寫一個只存「非零格子」的稀疏矩陣模組，支援設值與查詢。

請繳交 sparse.h 與 sparse.c。列與欄皆從 0 開始編號，介面如下：

typedef struct sparse sparse;
void sparse_init(sparse *m, int rows, int cols);
void sparse_set(sparse *m, int r, int c, long long v);
long long sparse_get(sparse *m, int r, int c); /* 0 if unset */

數值請使用 long long。評測用的驅動程式會先把所有非零元素以 sparse_set 載入，再逐筆呼叫 sparse_get 回答查詢。

輸入格式（驅動程式）

• 第一行：rows cols n，矩陣的列數、欄數，以及接下來要載入的元素個數。
• 接下來 n 行：r c v，在第 r 列第 c 欄設為 v（long long）。
• 下一行：整數 Q，查詢次數。
• 接下來 Q 行：每行 get r c，要求輸出 (r, c) 的值。

輸出格式

對每筆查詢輸出一行，為該位置目前的值；從未設定過的位置輸出 0。

限制

• 壓力測資中 1 ≤ rows, cols ≤ 100
• 0 ≤ n ≤ 200
• 0 ≤ Q ≤ 50
• 壓力測資中 −10 ≤ v ≤ 10
• 0 ≤ r < rows、0 ≤ c < cols

行為規則

• sparse_init 之後，所有位置的值都是 0。
• sparse_set(r, c, v) 且 v ≠ 0：該位置若沒有元素就新增，已有元素就改成 v（覆寫，不是累加）。
• sparse_set(r, c, 0)：該位置若有元素就移除，否則什麼都不做。
• 對沒有元素的位置呼叫 sparse_get 要回傳 0。
• 同一個位置在輸入中出現多次時，以最後一次的值為準。

提示

資料量不大，每列掛一條以欄號排序的鏈結串列，或用雜湊表，都已足夠，不需要平衡樹。

範例

範例 1

輸入

3 3 3
0 0 1
1 2 2
2 1 3
3
get 0 0
get 1 1
get 2 1

輸出

1
0
3

說明

三個非零格是 (0,0)=1、(1,2)=2、(2,1)=3；沒設定過的 (1,1) 回傳 0。

範例 2

輸入

2 2 1
0 1 5
2
get 0 1
get 1 0

輸出

5
0

說明

只有 (0,1)=5 一格非零，查詢 (1,0) 得到 0。

範例 3

輸入

2 2 2
0 0 5
1 1 3
3
get 0 0
get 0 1
get 1 1

輸出

5
0
3

說明

矩陣只有 (0,0)=5 與 (1,1)=3 兩個非零格；沒設定過的 (0,1) 回傳 0。

範例 4

輸入

1 1 0
1
get 0 0

輸出

0

說明

一個元素都沒載入，整張矩陣都是 0。

範例 5

輸入

2 2 3
0 0 5
0 0 9
1 0 2
2
get 0 0
get 1 0

輸出

9
2

說明

(0,0) 先被設為 5 再被設為 9，後者覆寫前者，所以答案是 9，不是 14。

範例 6

輸入

3 3 2
0 2 -7
2 0 4
4
get 0 2
get 2 0
get 1 1
get 2 2

輸出

-7
4
0
0

說明

負數照樣儲存並原樣回傳。