hdu1035---Robot Motion解题报告(DFS模拟)
Robot Motion链接
输入:地图行数row,列数col,以及机器人初始位置为(1,n)
输出:
1.机器人能走出:机器人走出地图的步数
2.机器人不能走出:求机器人在地图中走入一个n步的循环+之前单独走的步数
思路:简单的方向模拟就好了,每个走的点记录一次
两个返回条件:
1.经过重复点,则记录之前起点到当前重复点的距离abs(sx - fx) + abs(sy - fy)
再用总步数减去它就得循环步数
2.走出地图,则把step1一步步+1就行
AC Code:
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<list>
#define mod 998244353
#define INF 0x3f3f3f3f
#define Min 0xc0c0c0c0
#define mst(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i = a; i < b; i++)
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 5;
int row, col, s_col, sx, sy;
char maps[12][12];
bool vis[12][12];
bool flag;
const int dis[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
//typedef pair<int, int> Rob;
int step1, step2;
int get_dis(char c){
if(c == 'N'){
return 0;
}
if(c == 'E'){
return 1;
}
if(c == 'S'){
return 2;
}
if(c == 'W'){
return 3;
}
}
void dfs(int x, int y){
if(x < 1 || x > row || y < 1 || y > col){
//cout<<x<<" "<<y<<endl;
flag = true;
return ;
}
else{
//cout<<get_dis(maps[x][y])<<endl;
int fx = x + dis[get_dis(maps[x][y])][1];
int fy = y + dis[get_dis(maps[x][y])][0];
//cout<<sx<<" "<<sy<<endl;
//cout<<fx<<" "<<fy<<endl;
if(!vis[fx][fy]){
vis[fx][fy] = 1;
step1++;
}
else{
step1++;
step2 = abs(sx - fx) + abs(sy - fy);
return ;
}
dfs(fx, fy);
}
}
int main(){
//freopen("c1.txt", "w", stdin);
//freopen("c2.txt", "r", stdout);
ios::sync_with_stdio(false);
while(cin>>row>>col>>s_col){
if(row == 0 && col == 0 && s_col == 0){
break;
}
for(int i = 1; i <= row; i++){
for(int j = 1; j <= col; j++){
cin>>maps[i][j];
}
}
sx = 1, sy = s_col;
step1 = 0, step2 = 0;
flag = false;
mst(vis);
vis[sx][sy] = 1;
dfs(sx, sy);
if(flag){
cout<<step1<<" step(s) to exit"<<endl;
}
else {
cout<<step2<<" step(s) before a loop of "<<step1- step2<<" step(s)"<<endl;
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}