12516 - Cinema-

Cinema-cola

A group of Z friends is going to the movies. They have already reserved some specific locations in the theater. As a kind of ritual, every friend likes to drink something while seeing the film.

Locations at the theater are disposed in a rectangular array of R rows and C columns. Rows are named sequentially with English capital letters (`A', `B', `C', ...). Columns are named with integers (1, 2, 3, ..., C). Then, locations are identified by a string formed by the corresponding row letter and column number of the location.

Locations at the theater are chairs with plastic supports at both arms, to put a drink on each one. Supports are shared by neighbor locations but, of course, it is expected that at most one person uses a support to put his/her drink, but there is no etiquette rule that forces someone to use the right or the left support of his/her chair.

As a matter of example, the next figure illustrates a theater with 3 rows and 5 columns. Locations are depicted with rectangular forms, and supports with circles at both sides of them.

The group of friends goes to occupy the reserved locations. Before them, some persons came and occupied some of the locations (different from those of the group) and everyone used one support for a drink. Is it possible that the group of friends sit at their locations warranting that everyone in the group can put his/her drink on a support that corresponds to his/her location? Clearly, sometimes the spectators that came before the group may have used the supports in such a way that not everyone in the group may use a support for his/her drink.

Input 

There are several cases to consider. Each case begins with a line with two integer numbers R and C, indicating the number of rows and columns in the theater ( 1 R 26, 2 C 99). The next line contains an integer number P indicating the number of persons that came to the theater before than the group ( 0 P R ^. C - 1). Each one of the next P lines contains two text strings; the first one corresponds to the location id (one letter, one integer numeral) and, the second one is an one-character string with a sign `-' or a sign `+' denoting the fact that the person is using the left or the right support of his/her location, respectively. The next line contains an integer number Z indicating the number of persons in the group of friends ( 1 Z R ^. C - P). Finally, each one of the following Z lines contains the locations' ids of the reserved seats for the group of friends. In each case, you may suppose that the given identifiers are distinct and that every drink was put in an empty support before the friends came.

Each line in a case description has no leading spaces and items on a line are separated by exactly one space. There are no spaces at the end of any line. Input ends with a line with two `0' values.

Output 

For each case output a line with one of the texts `YES' or `NO' depending on the fact that the group of friends can occupy their seats and use some of the supports to place their drinks with the constraints imposed by the already occupied seats and supports.

Sample Input 

3 5
3
A3 -
B1 -
B4 -
4
A1
A2
B2
B3
3 5
3
A3 -
B1 +
B4 -
4
A1
A2
B2
B3
0 0

Sample Output 

YES
NO

---

題目描述：

電影院的座位，飲料杯可以放置該位置左側或者右側，由於沒有特別規定，可以隨意擺放，但是不能偷喝別人的。現在已經有些人入場座好，並且已經將他們的杯子放好。

現在，入場的是你的朋友們，問每個人是否都可以有自己放置飲料杯的位置。

題目解法：

要說是 greedy 也可以，先將已經入場的飲料杯位置標記。

接著對每一排座位，由左而右掃描，盡可能放左側，不行就放右側。


#include <stdio.h>

int main() {
    int R, C, P, Z;
    int i, j, k;
    char s1[10], s2[10];
    while(scanf("%d %d", &R, &C) == 2 && R+C) {
        int seat[26][105] = {};
        int drinks[26][105] = {};
        scanf("%d", &P);
        while(P--) {
            scanf("%s %s", s1, s2);
            int r, c;
            r = s1[0]-'A';
            sscanf(s1+1, "%d", &c);
            if(s2[0] == '-')
                drinks[r][c-1] = 1;
            else
                drinks[r][c] = 1;
        }
        scanf("%d", &Z);
        while(Z--) {
            scanf("%s", s1);
            int r, c;
            r = s1[0]-'A';
            sscanf(s1+1, "%d", &c);
            seat[r][c] = 1;
        }
        int errflag = 0;
        for(i = 0; i < R; i++) {
            for(j = 1; j <= C; j++) {
                if(seat[i][j]) {
                    if(drinks[i][j-1] == 0)
                        drinks[i][j-1] = 1;
                    else if(drinks[i][j] == 0)
                        drinks[i][j] = 1;
                    else
                        errflag = 1;
                }
            }
        }
        puts(errflag ? "NO" : "YES");
    }
    return 0;
}