推 rock1985:我問題解決了 感謝你 11/12 07:59
其實以前我也是對線段做處理，花了很多coding時間才搞定。
但是如今我想提供一個比較簡單的方法。
===================教學開始===========================
1.資料結構
測資的數值小於10000，於是就開個
const int SIZE = 10005;
char graph[SIZE][SIZE];
以UVa限制的記憶體來說是足夠的。
2.標記
對於L，H，R我們定義4個Macro
#define LEFT (1 << 0)
#define RIGHT (1 << 1)
#define LEFT_STRAIGHT (1 << 2)
#define RIGHT_STRAIGHT (1 << 3)
LEFT無疑的就是上升的標記，RIGHT就是下降的標記。
STRAIGHT英文意思是筆直的，我們用來定義橫線。
所以，LEFT_STRAIGHT就是該點的左邊有線相連，
RIGHT_STRAIGHT就是該點的右邊有線相連。
對於下面的圖形來說，
點1----點2----點3
| |
| |
| |
點1 |= RIGHT_STRAIGHT;
點2 |= LEFT_STRAIGHT | RIGHT_STRAIGHT;
點3 |= LEFT_STRAIGHT;
另外，要特別注意L == R的情況，
此時就只有
for(int i = 0; i <= H; ++i) {
graph[i][L] |= LEFT;
}
和
for(int i = H; i >= 0; --i) {
graph[i][R] |= RIGHT;
}
就沒有橫線給值的情況。
3.情境模擬
定義v(vertical)和h(horizontal)為graph[v][h]作用的index。
再寫一個函式isSet()判斷該bit是否有被設起。
如果是以isSet(graph[v][h], LEFT)來判斷的話，
函式就可以寫成
bool isSet(char c, char b) {
return ((c & b) > 0);
}
3.1.上升要到什麼時候停止呢？
v一直加1，判斷isSet(graph[v][h], LEFT)為true，直到為false停止。
3.2.下降要到什麼時候停止呢？
v一直減1，直到isSet(graph[v][h], RIGHT_STRAIGHT)為true停止，
代表右邊有相連。
或是 v一定要 >= 0，當v == 0時停止。
3.3.橫向移動要到什麼時候停止呢？
h一直加1，
3.3.1.如果if(isSet(graph[v][h], LEFT))為true就跳出，代表又要往上升了。
有上升就有下降，
3.3.2.如果isSet(graph[v][h], RIGHT)為true，並且
isSet(graph[v][h], LEFT_STRAIGHT)為true 並且
isSet(graph[v][h], RIGHT_STRAIGHT)為false
三者條件同時發生時，就代表要下降了。
剩下的輸出和片段組合我想應該都不難。
用這樣的方法，不消20分鐘就可以搞定，
但是由於開陣列很大的緣故，
AC秒數大約是1.2s，會是原本方法的10倍多左右。
就由原po自行考量coding的難易度和時間的花費。
Bleed
※ 引述《rock1985 (疾風)》之銘言：
: 題號：
: 105 - The Skyline Problem
: 遇到的問題：
: WA
: 有問題的code： (請善用置底文的標色功能)
: #include <iostream>
: using namespace std;
: int main()
: {
: int L,H,R;
: int counter = 0;
: int temp_pre,temp_curr;
: int min = 20000,max = 0;
: int building[10001] = {0};
: while(cin>>L>>H>>R)
: {
: if(min>L)
: min = L;
: if(max<R)
: max = R;
: for(int i = L ; i < R ; i++)
: {
: if(building[i] < H)
: building[i] = H;
: }
: counter++;
: }
: bool check = true;
: temp_pre = building[min];
: cout<<min<<" "<<temp_pre<<" ";
: for(int j = min+1 ; j <= max ; j++)
: {
: temp_curr = building[j];
: if(check) //check == true
: {
: if(temp_curr == 0)
: {
: check = false;
: cout<<j<<" "<<temp_curr;
: }else
: {
: if(temp_curr != temp_pre)
: {
: cout<<j<<" "<<temp_curr<<" ";
: temp_pre = temp_curr;
: }
: }
: }
: else
: {
: if(temp_curr == 0)
: {
: //do nothing
: }else
: {
: check = true;
: temp_pre = temp_curr;
: cout<<" "<<j<<" "<<temp_curr<<" ";
: }
: }
: }
: return 0;
: }
: 補充說明：
: 我的做法是把輸入都存到陣列
: 在印出來
: 請大家幫我看一下我的盲點在哪
: 感謝大家 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.125.81
※ 編輯: bleed1979 來自: 114.43.125.81 (11/11 19:37)
※ 編輯: bleed1979 來自: 114.43.125.81 (11/11 19:41)