UVa 825 - Walking on the Safe Side(단순 DP+데이터 읽기)

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. 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 3 5 4 Sample Output 파일 제목: 한 N*M의 격자에서 왼쪽 상단에서 오른쪽 하단까지 지나갈 수 없는 부분이 있어 가장 짧은 줄의 수를 구한다.
분석: 간단하게 보면 이것이 바로 간단한 DP다.상태 f[i][j]는 (i, j)까지 가는 방안의 수를 표시하고 왼쪽으로 가고 아래로 가는 상황만 고려한다.
제목 구덩이: 이렇게 쓰면 제목이 물 같고 AC가 되는 것 같지만 사실 곰곰이 생각해보면 아직 고려하지 못한 경우가 많거나 제목 표현이 완비된 것 같다.처음에는 생각을 많이 했는데, 예를 들어 함정 때문에 오른쪽으로 가다가 왼쪽으로 가야 종점에 도착할 수 있다. 제목과 걷는 방향을 정하기 때문에 도착할 수 있는 최단길만 말했기 때문이다.이렇게 되면 위의 방식으로 옮기면 정확한 결과가 나오지 않는다.그러나 이런 데이터가 나오지 않았다는 사실이 증명되었다...그리고 제목은 데이터 범위를 말하지 않았어요...너무 규범에 맞지 않는다.
수확: 그래서 이 문제의 주요 수확은 get이 새로운 읽기 방식을 얻었습니다...stringstream 이렇게 문자열을 처리하면 문자열에서 빈칸으로 구분된 숫자를 직접 추출할 수 있습니다.

#include <sstream>
string s;
int main()
{
    getline(cin,s);
    stringstream ss(s);
    while(ss>>num) a[num]=1; //                        
}

제목 소스:

// Created by ZYD in 2015.
// Copyright (c) 2015 ZYD. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define Size 100000
#define ll long long
#define mk make_pair
#define pb push_back
#define mem(array) memset(array,0,sizeof(array))
typedef pair<int,int> P;
string s;
int dp[1005][1005],used[1005][1005],n,m,t;
int main()
{
    freopen("in.txt","r",stdin);
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        mem(used);
        mem(dp);
        for(int i=1;i<=n;i++)
        {
            int x,lie;
            scanf("%d",&x);
            getline(cin,s);
            stringstream ss(s);
            while(ss>>lie) used[x][lie]=1;
        }
        dp[0][1]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            if(!used[i][j])
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        cout<<dp[n][m]<<endl;   
        if(t) cout<<endl;
    }
    return 0;
}