蓝桥杯真题递增序列求思路纠正
题目:
对于一个字母矩阵,我们称矩阵中的一个递增序列是指在矩阵中找到两个字母,它们在同一行,同一列,或者在同一 45 度的斜线上,这两个字母从左向右看、或者从上向下看是递增的。
例如,如下矩阵中
LANN
QIAO
有LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、AN等 13 个 递增序列。注意当两个字母是从左下到右上排列时,从左向右看和从上向下看 是不同的顺序。
对于下面的 30 行 50 列的矩阵,请问总共有多少个递增序列?
VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX
求指点,到底是哪里的思路出错了,答案应为52800,下方为我自己的Java代码,使用样例中的LANN QIAO可以正确输出13,但题中的30行50列矩阵输出为59614,多于正确答案,望各位提供指点。
package lanqiao;
import java.util.Scanner;
public class Main{
public static int c1=0;
public static int c2=0;
public static int N=0;
public static void main(String[] args){
Scanner sca=new Scanner(System.in);
StringBuilder[] S=new StringBuilder[30];
for(int i=0;i<30;i++){
S[i]=new StringBuilder(sca.nextLine());
}
sca.close();
System.out.println(count(S));
}
public static int count(StringBuilder[] S){
int C=0;
System.out.println(S);
for(int i=0;i<S.length;i++){
for(int j=0;j<S[i].length();j++){
for(int k=i+1;k<S[i].length();k++){
if(S[i].charAt(j)<S[i].charAt(k)){
C++;
}
}
for(int k=i+1;k<S.length;k++){
if(S[i].charAt(j)<S[k].charAt(j)){
C++;
}
}
for(int k=1;k+i<S.length&&k+j<S[i].length();k++){
if(S[i].charAt(j)<S[i+k].charAt(j+k)){
C++;
}
}
for(int k=1;k+i<S.length&&j-k>=0;k++){
if(S[i].charAt(j)!=S[i+k].charAt(j-k)){
C++;
}
}
}
}
return C;
}
}