Abfrage über SPOJ TOURIST

Question

Problemstellung:

Ein fauler Tourist will, ohne dabei einen Schritt weiter als notwendig, so viele interessante Orte in einer Stadt wie möglich besuchen. Von aus seinem Hotel, in der nordwestlichen Ecke der Stadt gelegen, will er einen Spaziergang in die südöstliche Ecke der Stadt machen und dann zurück gehen. Wenn er in die südöstliche Ecke läuft, wird er nur nach Osten oder nach Süden gehen, und wenn er zurück in die nordwestliche Ecke geht, wird er nur nach Norden oder Westen wandern. Nach dem Studium des Stadtplans stellt er fest, dass die Aufgabe nicht so einfach ist, weil einige Bereiche blockiert sind. Deshalb hat er Sie gebeten, ein Programm zu schreiben, um sein Problem zu lösen.

Angesichts der Stadtkarte (ein 2D-Raster), wo die interessanten Standorte und blockierten Bereichen markiert sind, bestimmen Sie die maximale Anzahl von interessanten Standorten, die er besuchen kann. Zweimal besuchte Orte werden nur einmal gezählt.

Eingang

Die erste Zeile in dem Eingang enthält die Anzahl der Testfälle (höchstens 20). Dann folge den Fällen. Jeder Fall beginnt mit einer Zeile mit zwei Ganzzahlen, W und H (2 ≤ W, H ≤ 100), die Breite und Höhe der Stadtplan. Dann H Linien folgen, die jeweils eine Zeichenkette mit W Zeichen mit folgender Bedeutung enthalten:

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

Sie können davon ausgehen, dass die obere linke Ecke (Anfangs- und Endpunkt) und unteren rechten Ecke (Wendepunkt) sind begehbar, und zwischen ihnen existiert ein begehbarer Weg der Länge H + W - 2.

Ausgabe

Für jeden Testfall, Ausgabe einer Zeile eine einzelne ganze Zahl enthält: die maximale Anzahl an interessanten Orten die faulen Touristen besuchen können.

Beispiel

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

Ausgang: 7 8

Meine Lösung:

#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; 
} 
} 

Ich habe noch nicht verwendet memoization wie ich gerade bin versucht, eine Backtrack-Funktion zu schreiben. Aber ich bekomme eine falsche Antwort für den ersten Testfall. Die richtige Antwort ist 7, aber dieser Code druckt 10. Was ist falsch in dieser rekursiven Lösung?

Answer 1

Sie sollten Sz1 und Sz2 tauschen.

Die erste Zeile der Eingabe gibt die Anzahl der Spalten bzw. die Anzahl der Zeilen an. Aber du hast sie in umgekehrter Reihenfolge behandelt.