第七个测试点错了,输入:
4 4 0
3 3 3 4
输出:
170
答案:89
#include <iostream>
#include <map>
using namespace std;
struct Point{
int x;
int y;
};
Point cannot[11];
bool cannotMap[11][11];
int n, m, k;
bool isValid(int x, int y){
if(x<0||y<0||x>=n||y>=m) return false;
return true;
}
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
bool vis[6][6]={0};
int ans=0;
Point s, f;
void dfs(int x, int y){
if(x==f.x&&y==f.y){
ans++;
printf("%d %d\n", x, y);
printf("------------------------------------\n");
return;
}
Point p;
p.x=x;
p.y=y;
if(cannotMap[p.y][p.x]==1||!isValid(y, x)) return;
printf("%d %d\n", x, y);
for(int i=0;i<4;i++){
if(!vis[x+dx[i]][y+dy[i]]){
vis[x+dx[i]][y+dy[i]]=1;
dfs(x+dx[i], y+dy[i]);
vis[x+dx[i]][y+dy[i]]=0;
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
scanf("%d%d%d%d", &s.x, &s.y, &f.x, &f.y);
s.x--;
s.y--;
f.x--;
f.y--;
for(int i=0;i<k;i++){
scanf("%d%d", &cannot[i].x, &cannot[i].y);
cannotMap[cannot[i].y-1][cannot[i].x-1]=1;
}
Point t;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(cannotMap[i][j]==1) continue;
cannotMap[i][j]=0;
}
}
if(cannotMap[f.y][f.x]){
printf("0");
return 0;
}
vis[0][0]=1;
dfs(s.x, s.y);
printf("%d", ans);
return 0;
}
dalao们帮我看看