求助! 90分 第二个点WA了

up_p @ 2024-10-08 21:20:44

#include<bits/stdc++.h>
//#define int long long
#define inf LONG_LONG_MAX
#define endl '\n'
#define ls(t) (t<<1)
#define rs(t) (t<<1|1)
using namespace std;
inline int read(){
    int x=1,sum=0;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            x=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        sum=(sum<<3)+(sum<<1)+(ch^48);
        ch=getchar();
    }
    return x*sum;
}
int n,m,x,y,sum,t,su[100105],dp[1015][1015];
char c;
bool vis[1015][1015];
int a[1015][1015];
int dx[6]={0,1,-1,0,0};
int dy[6]={0,0,0,1,-1};
bool check(int x,int y){
    return (x>=1&&x<=n&&y>=1&&y<=n&&(vis[x][y]==0));
}
void summ(int x,int y,int k){
    sum++;
    vis[x][y]=1;
    dp[x][y]=k;
    for(int i=1;i<=4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if((check(xx,yy)==1)&&((a[xx][yy]^a[x][y])==1)){
            summ(xx,yy,k);
        }
    }
}
signed main(){
    memset(dp,0,sizeof(dp));
    memset(vis,0,sizeof(vis));
    n=read();m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>c;
            a[i][j]=c-'0';
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(dp[i][j]==0){
                t++;
                summ(i,j,t);
                su[t]=sum;
                sum=0;
            }
        }
    }
    for(int i=1;i<=m;i++){
        x=read();y=read();
        cout<<su[dp[x][y]]<<endl;
    }
    return 0;
}

by zihao20111212 @ 2024-10-08 22:02:04

为什么是signed main()?

by nannangua @ 2024-10-09 17:25:10

这题要dfs两次（用两个dfs函数）,一个判断vis的1，一个0，回溯两遍

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn=1e3+3;
char a[maxn][maxn];
int vis[maxn][maxn],ans=0,cnt[maxn][maxn];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,T,c[maxn][maxn];
bool check(int x,int y)
{
    return x<=n && x>=1 && y<=n && y>=1;
}
void dfs1(int x,int y)
{
    ans++;
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(check(tx,ty) && vis[tx][ty]==0)
        {
            if((a[x][y]=='1' && a[tx][ty]=='0') || (a[x][y]=='0' && a[tx][ty]=='1')) 
            {
                dfs1(tx,ty);
            }
        }
    }
}
void dfs2(int x,int y)
{
    vis[x][y]=0;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(check(tx,ty) && vis[tx][ty]==1)
        {
            if((a[x][y]=='1' && a[tx][ty]=='0') || (a[x][y]=='0' && a[tx][ty]=='1')) 
            {
                cnt[tx][ty]=ans;
                dfs2(tx,ty);
            }
        }
    }
} 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>T;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    int x,y;
    while(T--)
    {
        ans=0;
        cin>>x>>y;  
        if(cnt[x][y]!=0) 
        {
            cout<<cnt[x][y]<<endl;
            continue;
        }
        dfs1(x,y);
        cout<<ans<<endl;
        dfs2(x,y);  
    }
    return 0;
}

可以这样写

by up_p @ 2024-10-13 14:05:22

@nannangua 6

by up_p @ 2024-10-13 14:06:45

@zihao20111212 因为不能long long main()

by up_p @ 2024-10-13 14:25:41

找到原因了--数组开小了

此贴结