Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 水题，一个DFS搞定，没什么BT数据

Posted by KatrineYang at 2016-11-15 13:56:20 on Problem 1522
```这题要是有BT数据，可以有10^10个点，输入都读不完就铁定TLE
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>

using namespace std;

int cnt;
int n;
map<long long int, int> idx;
int qd, zd;

int getIdx(){
int Temp;
scanf("%d",&Temp);
long long int temp = Temp;
if(temp == -1) return -1;
for(int i = 1; i < n; i++){
int tmp;
scanf("%d", &tmp);
temp *= 10;
temp += tmp;
}
map<long long int, int>::iterator it = idx.find(temp);
if(it != idx.end()) return it->second;
idx.insert(pair<long long int, int>(temp, cnt));
cnt ++;
return cnt-1;
}

bool dfs(int q, bool *used){
used[q] = 1;
if(q == zd) return 1;
for(int i = 0; i < adjNum[q]; i++){
}
return 0;
}

int main(int argc, char **argv){
int ct = 0;
while(1){
cin >> n;
if(!n) break;
ct++;
cout << "Maze #" << ct << " can";
cnt = 0;
idx.clear();
for(int i = 0; i < 10000; i++) adjNum[i] = 0;
qd = getIdx(), zd = getIdx();
int x,y;
while((x = getIdx()) != -1){
y = getIdx();
}
bool used[10000] = {0};
if(!dfs(qd, used)) cout << "not";
cout << " be travelled" << endl;
}

return 0;
}```

Followed by: