想吃冰卻又敏感保護不足?5檔高息股比定存強10倍攝影界美人正妹指定相機款老伯送飲料 遭學生糾察...
2012-05-03 06:55:08 人氣(529) | 回應(1) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][DP] 825 - Walking on the Safe Side

0
收藏
0
推薦


  Walking on the Safe Side 

Square City is a very easy place for people to walk around. The two-way streets run North-South or East-West dividing the city into regular blocks. Most street intersections are safe for pedestrians to cross. In some of them, however, crossing is not safe and pedestrians are forced to use the available underground passages. Such intersections are avoided by walkers. The entry to the city park is on the North-West corner of town, whereas the railway station is on the South-East corner.


Suppose you want to go from the park to the railway station, and do not want to walk more than the required number of blocks. You also want to make your way avoiding the underground passages, that would introduce extra delay. Your task is to determine the number of different paths that you can follow from the park to the station, satisfying both requirements.

The example in the picture illustrates a city with 4 E-W streets and 5 N-S streets. Three intersections are marked as unsafe. The path from the park to the station is 3 + 4 = 7 blocks long and there are 4 such paths that avoid the underground passages.

epsfbox{p825.eps}

Input 

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.


The first line of the input contains the number of East-West streets W and the number of North-South streets N. Each one of the following W lines starts with the number of an East-West street, followed by zero or more numbers of the North-South crossings which are unsafe. Streets are numbered from 1.

Output 

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.


The number of different minimal paths from the park to the station avoiding underground passages.

Sample Input 

1

4 5
1
2 2
3 3 5
4

Sample Output 

4

 

#include <stdio.h>
#include <iostream>
#include <sstream>
using namespace std;

int main() {
    int t, n, m, x, y;
    string line;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        int map[101][101] = {}, i, j;
        map[0][1] = 1;
        getchar();
        for(i = 1; i <= n; i++) {
            getline(cin, line);
            stringstream sin(line);
            sin >> x;
            while(sin >> y) {
                map[x][y] = -1;
            }
        }
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= m; j++) {
                if(map[i][j] == -1)
                    continue;
                if(map[i][j-1] != -1)
                    map[i][j] += map[i][j-1];
                if(map[i-1][j] != -1)
                    map[i][j] += map[i-1][j];
            }
        }
        printf("%d\n", map[n][m]);
        if(t)
            puts("");
    }
    return 0;
}


825Walking on the Safe Side
台長:Morris
人氣(529) | 回應(1)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][SSSP] 10986 - Sending email
此分類上一篇:[UVA][Trie] 902 - Password Search

Zero
你好,我在你上一個Blog看到這一題,又得知你已經換成這個Blog的消息,所以我就跑來這邊留言,看到時有點驚訝,怎麼....C變成C++?

我想請問你舊站那篇的這行程式碼:

scanf("%d %d ",&n1,&m1);/*神奇的空格不可忽略*/

請問那個空格是哪個空格,有甚麼效果?
2012-07-18 15:36:13
版主回應
那個方法, 可以將 '\n' 讀掉,
因此會在最後一個 %d 後���多一個空白,
2012-07-18 19:42:39
我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文