Submission #13250

#	Time	Username	Problem	Language	Result	Execution time	Memory
13250		dohyun0324	K-th path (IZhO11_kthpath)	C++98	0 / 100	0 ms	1352 KiB

kthpath

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
char a[40][40];
int p,d[61][31][31],ch[30],num[40][40];
int r,n,m,k,cnt;
char dap[61],top;
int main()
{
    int i,j;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%s",&a[i]);
        for(j=m;j>=1;j--) a[i][j]=a[i][j-1];
    }
    num[n+1][m]=1;
    for(i=n;i>=1;i--){
        for(j=m;j>=1;j--){
            num[i][j]=num[i+1][j]+num[i][j+1];
        }
    }
    scanf("%d",&k); d[0][1][1]=1; dap[++top]='a';
    while(1){
        r++; memset(ch,0,sizeof ch);
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                d[r][i][j]+=d[r-1][i-1][j]+d[r-1][i][j-1];
                ch[a[i][j]-'a'+1]+=d[r][i][j]*num[i][j];
            }
        }
        for(i=1;i<=26;i++){
            if(cnt+ch[i]>k-1) break;
            cnt+=ch[i];
        }
        memset(d[r],0,sizeof d[r]); p=i;
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                if(a[i][j]-'a'+1==p) d[r][i][j]+=d[r-1][i-1][j]+d[r-1][i][j-1];
            }
        }
        dap[++top]=char(p+'a'-1);
        if(r==n+m-2) break;
    }
    for(i=1;i<=top;i++) printf("%c",dap[i]);
    return 0;
}

Compilation message (stderr)

kthpath.cpp: In function 'int main()':
kthpath.cpp:14:25: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[40]' [-Wformat=]
         scanf("%s",&a[i]);
                         ^
kthpath.cpp:23:44: warning: array subscript has type 'char' [-Wchar-subscripts]
     scanf("%d",&k); d[0][1][1]=1; dap[++top]='a';
                                            ^
kthpath.cpp:42:18: warning: array subscript has type 'char' [-Wchar-subscripts]
         dap[++top]=char(p+'a'-1);
                  ^
kthpath.cpp:12:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
                         ^
kthpath.cpp:14:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&a[i]);
                          ^
kthpath.cpp:23:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&k); d[0][1][1]=1; dap[++top]='a';
                   ^

• Subtask 1: 0 / 100