poj3984(经典dfs)

题目链接:http://poj.org/problem?id=3984

分析:直接深搜从起点到终点,如何取最短路线,其实只要优先向下或向右走即可。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 100010
using namespace std;
int s[][];
stack<int>s1,s2;
int vis[][];
int judge(int a,int b)
{
return a>=&&a<&&b>=&&b<&&s[a][b]==&&!vis[a][b];
}
int dfs(int x,int y)
{
if(x==&&y==)
{
s1.push(x);s2.push(y);return ;
}
vis[x][y]=;
if(judge(x,y+)&&dfs(x,y+)||judge(x+,y)&&dfs(x+,y)||
judge(x-,y)&&dfs(x-,y)||judge(x,y-)&&dfs(x,y-))
{ s1.push(x);s2.push(y);return ;
}
else
{
return ;
}
return ;
}
void print()
{
while(!s1.empty())
{
printf("(%d, %d)\n",s1.top(),s2.top());
s1.pop();s2.pop();
}
}
int main()
{
memset(vis,,sizeof(vis));
for(int i=;i<;i++)
for(int j=;j<;j++)scanf("%d",&s[i][j]);
dfs(,);print();
}
上一篇:a 标签 跳转4种类型


下一篇:postgresql导入及导出