クエリに関するSPOJ TOURIST

Question

問題の声明：

は怠惰な観光客は、さらに一歩必要以上に行かなくても街できるだけ のように多くの興味深い場所を訪問することを望んでいます。都市の北西に位置する彼のホテルから を始めて、彼は を予定しており、街の南東に歩いて行くと に戻ってくる。南東の角まで歩いて行くと、彼は東に歩くか、または 南に戻り、北西の角に戻って歩くときには、彼は北または西に歩いて になります。都市地図を勉強した後、彼は一部の地域がブロックされているので、 の仕事はそれほど簡単ではないことを認識しています。したがって彼は あなたの問題を解決するためのプログラムを書くように親切に依頼しています。興味深い場所と ブロックされた領域がマークされている（2Dグリッド）市内マップを考える

は、彼が訪問することができます面白い 場所の最大数を決定します。 2回訪れた場所は1回だけカウントされます。

入力

入力の最初の行のテストケース（せいぜい 20）の数を含んでいます。その後、ケースに従います。それぞれの場合は、 の2つの整数WとH（2≦W、H≦100）、市街地図 の幅と高さを含む行から始まります。そして、それぞれが次のような意味を持つW 文字の文字列を含む、Hラインに従ってください。

 
. Walkable area 
* Interesting location (also walkable area) 
# Blocked area

あなたは、左上隅（始点と終点）と 右下隅は（ターニングポイント）と仮定してよいですそれらの間には長さH + W-2の歩行可能な道具が存在することが示されている。

各テストケースに対する出力

、出力つの整数を含む行：怠惰な観光客が訪問することができ、興味深い場所の 最大数。

例

Input: 
    2 9 7 
*........ 
.....**#. 
..**...#* 
..####*#. 
.*.#*.*#. 
...#**... 
*........ 
5 5 
    .*.*. 
*###. 
*.*.* 
.###* 
.*.*.

出力：7 8

私のソリューション：

#include <iostream> 

using namespace std; 

char path[101][101]; 
int sz1,sz2; 
int solve(int a,int b,int i,int j){ 
if(a>=sz1||b>=sz2||i>=sz1||j>=sz2){ 
    return 0; 
    } 
    int c = 0; 
if(path[a][b]=='#'||path[i][j]=='#') 
    return -100; 
if(path[a][b]=='*'){ 
    c = 1; 
    } 
if(path[i][j]=='*'&&a!=i) 
    c++; 
int x =max(max(solve(a,b+1,i+1,j),solve(a+1,b,i+1,j)),max(solve(a,b+1,i,j+1),solve(a+1,b,i,j+1))); 

return x+c; 
} 

int main() 
{ 
int t; 
cin>>t; 
while(t--){ 
cin>>sz1>>sz2; 

for(int i=0;i<sz1;i++){ 
    for(int j=0;j<sz2;j++) 
     cin>>path[i][j]; 
} 

cout << solve(0,0,0,0) << endl; 
} 
} 

私はちょうどバックトラック関数を記述しようとしているように私はまだメモ化を使用していません。しかし、私は最初のテストケースで間違った答えを得ています。正解は7ですが、このコードは10を出力します。この再帰的な解決策では何が間違っていますか？

Answer 1

sz1とsz2を交換する必要があります。

最初の入力行は、それぞれ列数と行数を示します。しかし、あなたはそれらを逆の順序で扱いました。