10.10T5 vector模拟+getchar卡常

军训
(File IO): input:rect.in output:rect.out

Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits

Description

小L正在参加学校组织的军训。军训的操场是一个n*m的网格，每个网格开始时都没有人。每次军官会指定某些行和列，并在这些行和列的每个交界处都安排站上一名学生。但为了防止两名学生站到同一个网格中，军官每次指定的行和列并不会和之前指定过的重复。军官接到了上级的要求，需要将学生摆成特定的图案，那么军官能否达成要求呢？

Input

第一行一个整数T，表示数据组数。
接下来每个数据第一行两个整数n,m,意义如题面所述。
接下来n行，每行一个长度为n的字符串,其中第j个字符是’#’则代表i行j列的网格上要有学生，如果是’.’则代表没有。

Output

对于每组数据一行一个字符串“Yes”或者”No”，表示能否达到要求。

Sample Input

5 8

.#.#..#.

.....#..

.#.#..#.

#.#....#

.....#..

Sample Output

Yes

Data Constraint

n,m<=2000

vector拉行列两个表，然后行列模拟一下消除，遇到那种不存在的判No就行了

再有就是我不知道为啥被读入卡了，改getchar就过了。。。。

code：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<string>
 5 #define N 4000005
 6 using namespace std;
 7 int read() {
 8     int x=0,f=1;
 9     char c=getchar();
10     while(!isdigit(c)) {
11         if(c=='-')f=-1;
12         c=getchar();
13     }
14     while(isdigit(c)) {
15         x=(x<<1)+(x<<3)+c-'0';
16         c=getchar();
17     }
18     return x*f;
19 }
20 struct node {
21     int x, y;
22 } e[N];
23 int main() {
24     int T;
25     T=read();
26     while(T--) {
27         vector<int>hang[2005],lie[2005];
28         int checkhang[2003]={0},checklie[2003]={0};
29         int n,m;
30         int flag=0,cnt=0;
31         n=read(),m=read();
32         for(int i=1; i<=n; i++) {
33         /*    string kkk;
34             getline(cin,kkk);*/
35             for(int j=1; j<=m; j++) {
36                 char s=getchar();while(s!='#'&&s!='.')s=getchar();
37                 if(s=='#') {
38                     e[++cnt].x=i;
39                     e[cnt].y=j;
40                     hang[i].push_back(cnt);//在这一行，所以放进一个vector里面
41                     lie[j].push_back(cnt);//在这一列，所以放进vector里面
42                 }
43             }
44         }
45         for(int u=1; u<=cnt; u++) {
46             int i=e[u].x,j=e[u].y;
47             if(checkhang[i]||checklie[j])continue;
48             //    cout<<i<<" "<<j<<endl;
49             int temphang[2003],templie[2003];
50             int tot1=0,tot2=0;
51             for(int k=0; k<hang[i].size(); k++) { //同一行的
52                 templie[++tot2]=e[hang[i][k]].y;
53                 checklie[templie[tot2]]=1;
54             }
55             for(int k=0; k<lie[j].size(); k++) {//同一列的
56                 temphang[++tot1]=e[lie[j][k]].x;
57                 checkhang[temphang[tot1]]=1;
58             }
59             /*    for(int k=1; k<=tot1; k++) {
60                     if(flag)break;
61                     for(int l=1; l<=tot2; l++) {
62                         if(g[temphang[k]][templie[l]]=='#') {
63                             if(hang[temphang[k]].size()!=tot2)flag=1;
64                             if(lie[templie[l]].size()!=tot1)flag=1;
65                             if(flag)break;
66                             g[temphang[k]][templie[l]]='.';
67                         } else {
68                             flag=1;
69                             break;
70                         }
71                     }
72                 }*/
73             for(int k=1; k<=tot1; k++) {
74                 if(hang[temphang[k]].size()!=tot2) {
75                     flag=1;
76                     break;
77                 }
78             }
79             if(flag)break;
80             for(int l=1; l<=tot2; l++) {
81                 if(lie[templie[l]].size()!=tot1) {
82                     flag=1;
83                     break;
84                 }
85             }
86             if(flag)break;
87         }
88         if(flag)cout<<"No
";
89         else cout<<"Yes
";
90     }
91     return 0;
92 }

over