QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#378825#7057. Digital PathCaptainfly#WA 69ms35240kbC++201.9kb2024-04-06 14:51:142024-04-06 14:51:15

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 14:51:15]
  • 评测
  • 测评结果:WA
  • 用时:69ms
  • 内存:35240kb
  • [2024-04-06 14:51:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
#define mp make_pair
inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
const ll mod=1000000007;
ll qpow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}
inline int lcm(int a, int b){return a / gcd(a, b) * b;}
#define maxn 200010

int a[1010][1010],f[1010][1010];
int dir[4][2] = {0,1,0,-1,1,0,-1,0};
int n,m;

int dfs(int x,int y)
{
    if(f[x][y]) return f[x][y];
    for(int i=0;i<4;i++)
    {
        int xx = x+dir[i][0],yy = y+dir[i][1];
        if(xx<=0||yy<=0||xx>n||yy>m) continue;
        if(a[xx][yy]-a[x][y]==1) f[x][y] += dfs(xx,yy);
        f[x][y] %= mod;
    }
    if(!f[x][y]) return f[x][y] = 1;
    return f[x][y];
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            cin>>a[i][j];
    int ans = 0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int ff = 1,ff1 = 0;
            for(int k=0;k<4;k++)
            {
                int xx = i+dir[k][0],yy = j+dir[k][1];
                if(xx<=0||yy<=0||xx>n||yy>m) continue;
                if(a[xx][yy]-a[i][j]==-1) ff = 0;
                if(a[xx][yy]-a[i][j]==1) ff1 = 1;
            }
            if(ff&&ff1)
            {
                ans += dfs(i,j);
                ans %= mod;
            }
        }
    cout<<ans<<'\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
int t=1;
//cin>>t;
while(t--)
    solve();
return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5648kb

input:

3 5
1 2 3 8 7
-1 -1 4 5 6
1 2 3 8 7

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5668kb

input:

4 4
1 2 3 4
2 3 4 3
3 4 3 2
4 3 2 1

output:

16

result:

ok single line: '16'

Test #3:

score: 0
Accepted
time: 69ms
memory: 35240kb

input:

1000 1000
1000000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 ...

output:

990039586

result:

ok single line: '990039586'

Test #4:

score: -100
Wrong Answer
time: 4ms
memory: 6584kb

input:

146 237
1 1 1 1 1 1 2 3 4 5 1 1 4 1 1 2 3 1 1 1 2 1 1 1 4 1 1 2 3 4 5 6 7 1 1 1 1 2 3 1 2 3 1 2 3 6 7 1 1 1 1 2 1 1 1 2 1 1 1 2 1 1 2 3 1 2 3 1 1 2 1 1 1 2 1 2 3 4 1 1 1 2 1 2 1 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 3 4 5 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 2 1 1 1 1 2 3 1 1 1 1 ...

output:

155789

result:

wrong answer 1st lines differ - expected: '152287', found: '155789'