Hdu 4517 小小明系列故事——游戲的煩惱

第一種解法:

遍歷求解。num[i][j]代表i行j列之前一共有多少個'×'。然後再面積夾擊求解x*y、y*x是否滿足，x==y只需要判斷一次。

這種方法提交用C++，不要用G++，否則會超時。

[cpp]
#include <iostream>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
#include <algorithm>  
#include <stack>  
#include <queue>  
using namespace std; 
 
int map[2005][2005]; 
int num[2005][2005]; 
 
int main() 
{ 
#ifndef ONLINE_JUDGE  
    freopen("in.txt","r",stdin); 
#endif  
    int n,m,x,y; 
    while(scanf(" %d %d",&n,&m)!=EOF) 
    { 
        if(n+m == 0) break; 
        for(int i=0;i<=n;i++) 
        { 
            for(int j=0;j<=m;j++) 
            { 
                num[i][j] = 0; 
            } 
        } 
 
        scanf(" %d %d",&x,&y); 
        getchar(); 
        for(int i=1; i<=n; i++) 
        { 
            for(int j=1; j<=m; j++) 
            { 
                char c; 
                scanf("%c",&c); 
                if(c == '*') 
                { 
                    map[i][j] = 1; 
                } 
                else 
                { 
                    map[i][j] = 0; 
                } 
            } 
            getchar(); 
        } 
        for(int i=1; i<=n; i++) 
        { 
            for(int j=1; j<=m; j++) 
            { 
                if(map[i][j] == 1) 
                { 
                    num[i][j] = num[i-1][j] + num[i][j-1] - num[i-1][j-1] + 1; 
                } 
                else 
                { 
                    num[i][j] = num[i-1][j] + num[i][j-1] - num[i-1][j-1]; 
                } 
            } 
        } 
        int ans = 0; 
        int size = x*y; 
        for(int i=x; i<=n; i++) 
        { 
            for(int j=y; j<=m; j++) 
            { 
                //滿足x*y的擺放位置  
                if(num[i][j] - num[i-x][j] - num[i][j-y] + num[i-x][j-y] == size) 
                { 
                    ans++; 
                } 
            } 
        } 
        if(x!=y) 
        { 
            for(int i=y; i<=n; i++) 
            { 
                for(int j=x; j<=m; j++) 
                { 
                    //滿足x*y的擺放位置  
                    if(num[i][j] - num[i-y][j] - num[i][j-x] + num[i-y][j-x] == size) 
                    { 
                        ans++; 
                    } 
                } 
            } 
        } 
        printf("%d\n",ans); 
    } 
    return 0; 
} 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

int map[2005][2005];
int num[2005][2005];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int n,m,x,y;
    while(scanf(" %d %d",&n,&m)!=EOF)
    {
        if(n+m == 0) break;
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                num[i][j] = 0;
            }
        }

        scanf(" %d %d",&x,&y);
        getchar();
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                char c;
                scanf("%c",&c);
                if(c == '*')
                {
                    map[i][j] = 1;
                }
                else
                {
                    map[i][j] = 0;
                }
            }
            getchar();
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(map[i][j] == 1)
                {
                    num[i][j] = num[i-1][j] + num[i][j-1] - num[i-1][j-1] + 1;
                }
                else
                {
                    num[i][j] = num[i-1][j] + num[i][j-1] - num[i-1][j-1];
                }
            }
        }
        int ans = 0;
        int size = x*y;
        for(int i=x; i<=n; i++)
        {
            for(int j=y; j<=m; j++)
            {
                //滿足x*y的擺放位置
                if(num[i][j] - num[i-x][j] - num[i][j-y] + num[i-x][j-y] == size)
                {
                    ans++;
                }
            }
        }
        if(x!=y)
        {
            for(int i=y; i<=n; i++)
            {
                for(int j=x; j<=m; j++)
                {
                    //滿足x*y的擺放位置
                    if(num[i][j] - num[i-y][j] - num[i][j-x] + num[i-y][j-x] == size)
                    {
                        ans++;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

第二種方法:

二維DP，但是會MLE。

[cpp] view plaincopyprint?#include <iostream>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
#include <algorithm>  
#include <stack>  
#include <queue>  
using namespace std; 
 
int map[2005][2005]; 
int h[2005][2005]; 
int l[2005][2005]; 
int l2[2005][2005]; 
 
int main() 
{ 
#ifndef ONLINE_JUDGE  
    freopen("in.txt","r",stdin); 
#endif  
    int n,m,x,y; 
    while(scanf(" %d %d",&n,&m)!=EOF) 
    { 
        if(n+m == 0) break; 
        memset(h,0,sizeof(h)); 
        memset(l,0,sizeof(l)); 
        memset(l2,0,sizeof(l2)); 
        scanf(" %d %d",&x,&y); 
        getchar(); 
        for(int i=1; i<=n; i++) 
        { 
            for(int j=1; j<=m; j++) 
            { 
                char c; 
                scanf("%c",&c); 
                if(c == '*') 
                    map[i][j] = 1; 
                else 
                    map[i][j] = 0; 
            } 
            getchar(); 
        } 
        int ans = 0; 
        for(int i=1; i<=n; i++) 
        { 
            for(int j=1; j<=m; j++) 
            { 
                if(map[i][j] == 1) 
                { 
                    h[i][j] = h[i-1][j] + 1; 
                    if(h[i][j]>=x) 
                        l[i][j] = l[i][j-1] + 1; 
                    else 
                        l[i][j] = 0; 
                    if(h[i][j]>=y) 
                        l2[i][j] = l2[i][j-1] + 1; 
                    else 
                        l2[i][j] = 0; 
                    if(h[i][j]>=x && l[i][j]>=y) 
                        ans++; 
                    if(h[i][j]>=y && l2[i][j]>=x && x!=y) 
                        ans++; 
                } 
                else 
                { 
                    h[i][j] = l[i][j] = l2[i][j] = 0; 
                } 
            } 
        } 
        printf("%d\n",ans); 
    } 
    return 0; 
} 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

int map[2005][2005];
int h[2005][2005];
int l[2005][2005];
int l2[2005][2005];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int n,m,x,y;
    while(scanf(" %d %d",&n,&m)!=EOF)
    {
        if(n+m == 0) break;
        memset(h,0,sizeof(h));
        memset(l,0,sizeof(l));
        memset(l2,0,sizeof(l2));
        scanf(" %d %d",&x,&y);
        getchar();
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                char c;
                scanf("%c",&c);
                if(c == '*')
                    map[i][j] = 1;
                else
                    map[i][j] = 0;
            }
            getchar();
        }
        int ans = 0;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(map[i][j] == 1)
                {
                    h[i][j] = h[i-1][j] + 1;
                    if(h[i][j]>=x)
                        l[i][j] = l[i][j-1] + 1;
                    else
                        l[i][j] = 0;
                    if(h[i][j]>=y)
                        l2[i][j] = l2[i][j-1] + 1;
                    else
                        l2[i][j] = 0;
                    if(h[i][j]>=x && l[i][j]>=y)
                        ans++;
                    if(h[i][j]>=y && l2[i][j]>=x && x!=y)
                        ans++;
                }
                else
                {
                    h[i][j] = l[i][j] = l2[i][j] = 0;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

第三種：

改成滾動數組，變成一維DP。

[cpp]
#include <iostream>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
#include <algorithm>  
#include <stack>  
#include <queue>  
using namespace std; 
 
int map[2005][2005]; 
int h[2005]; 
int l[2005]; 
int l2[2005]; 
 
int main() 
{ 
#ifndef ONLINE_JUDGE  
    freopen("in.txt","r",stdin); 
#endif  
    int n,m,x,y; 
    while(scanf(" %d %d",&n,&m)!=EOF) 
    { 
        if(n+m == 0) break; 
        memset(h,0,sizeof(h)); 
        memset(l,0,sizeof(l)); 
        memset(l2,0,sizeof(l2)); 
 
        scanf(" %d %d",&x,&y); 
        getchar(); 
        for(int i=1; i<=n; i++) 
        { 
            for(int j=1; j<=m; j++) 
            { 
                char c; 
                scanf("%c",&c); 
                if(c == '*') 
                    map[i][j] = 1; 
                else 
                    map[i][j] = 0; 
            } 
            getchar(); 
        } 
        int ans = 0; 
        for(int i=1; i<=n; i++) 
        { 
            for(int j=1; j<=m; j++) 
            { 
                if(map[i][j] == 1) 
                { 
                    h[j] = h[j] + 1; 
                    if(h[j]>=x) 
                        l[j] = l[j-1] + 1; 
                    else 
                        l[j] = 0; 
                    if(h[j]>=y) 
                        l2[j] = l2[j-1] + 1; 
                    if(h[j]>=x && l[j]>=y) 
                        ans++; 
                    if(h[j]>=y && l2[j]>=x && x!=y) 
                        ans++; 
                } 
                else 
                { 
                    h[j] = l[j] = l2[j] = 0; 
                } 
            } 
        } 
        printf("%d\n",ans); 
    } 
    return 0; 
} 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

int map[2005][2005];
int h[2005];
int l[2005];
int l2[2005];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int n,m,x,y;
    while(scanf(" %d %d",&n,&m)!=EOF)
    {
        if(n+m == 0) break;
        memset(h,0,sizeof(h));
        memset(l,0,sizeof(l));
        memset(l2,0,sizeof(l2));

        scanf(" %d %d",&x,&y);
        getchar();
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                char c;
                scanf("%c",&c);
                if(c == '*')
                    map[i][j] = 1;
                else
                    map[i][j] = 0;
            }
            getchar();
        }
        int ans = 0;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(map[i][j] == 1)
                {
                    h[j] = h[j] + 1;
                    if(h[j]>=x)
                        l[j] = l[j-1] + 1;
                    else
                        l[j] = 0;
                    if(h[j]>=y)
                        l2[j] = l2[j-1] + 1;
                    if(h[j]>=x && l[j]>=y)
                        ans++;
                    if(h[j]>=y && l2[j]>=x && x!=y)
                        ans++;
                }
                else
                {
                    h[j] = l[j] = l2[j] = 0;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}