[TIOJ] 1230. 尋寶問題

題目連結:http://tioj.infor.org/problems/1230

---

本題就照著DFS就好了XD
更新:突然發現我這寫法是假解，還在思索真解怎麼寫。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

#define N 3000

int graph[N][N];

struct List{
	int x;
	int y;
	List* next;
	List(){
		next=NULL;
	}
	~List(){
		if(next!=NULL)delete next;
	}
};
bitset<N> walked[N];
lld DFS(int,int,List*);
void cList(List*);
int n,m;

int main(){
	scanf("%d%d\n",&n,&m);
	for(int i=0;i<n;i++){
		char inp[N+5];
		gets(inp);
		int inpSZ = strlen(inp);
		int ctt=0;
		for(int j=0;j<inpSZ;j++){
			if(inp[j]==' ')continue;
			if(inp[j]=='x'){
				walked[i][ctt]=1;
				graph[i][ctt++]=-100;
			}else{
				graph[i][ctt++]=inp[j]-'0';
			}
			if(ctt==m)break;
		}
	}
	auto Front = new List;
	lld ans = DFS(n-1,m-1,Front);
	cList(Front);
	delete Front;
	auto FrontFront = new List;
	lld wow = DFS(0,0,FrontFront);
	ans+=wow;
	printf("%lld",ans);
	return 0;
}

void cList(List* L){
	if(L==NULL) return;
	graph[L->x][L->y]=0;
	cList(L->next);
}

lld DFS(int x,int y,List* L){
	assert(x<=n-1&&y<=m-1&&!walked[x][y]);
	L->x=x;
	L->y=y;
	lld mm = 0;
	if(x+1<=n-1 && !walked[x+1][y]){
		auto nn = new List;
		walked[x][y]=1;
		int sub = DFS(x+1,y,nn);
		if(sub>=mm){
			delete L->next;
			mm=sub;
			L->next = nn;
		}else{
			delete nn;
		}
		walked[x][y]=0;
	}
	if(x-1>=0 && !walked[x-1][y]){
		auto nn = new List;
		walked[x][y]=1;
		int sub = DFS(x-1,y,nn);
		if(sub>=mm){
			delete L->next;
			mm=sub;
			L->next = nn;
		}else{
			delete nn;
		}
		walked[x][y]=0;
	}
	if(y+1<=m-1 && !walked[x][y+1]){
		auto nn = new List;
		walked[x][y]=1;
		int sub = DFS(x,y+1,nn);
		if(sub>=mm){
			delete L->next;
			mm=sub;
			L->next = nn;
		}else{
			delete nn;
		}
		walked[x][y]=0;
	}
	if(y-1>=0 && !walked[x][y-1]){
		auto nn = new List;
		walked[x][y]=1;
		int sub = DFS(x,y-1,nn);
		if(sub>=m){
			delete L->next;
			mm=sub;
			L->next = nn;
		}else{
			delete nn;
		}
		walked[x][y]=0;
	}
	walked[x][y]=0;
	return mm+graph[x][y];
}