백준 3190 C++

 

#include 
#include 
#include 

using namespace std;

const int MAX = 100;
int n, applenum;
int location[MAX][MAX];
int ans = 0;
list<pair<int,pair< int,int>>> currentloc;
int visited[MAX][MAX];

int dfs(int c, char dir) {
int time = c - ans;
for (int i = 0; i < time; i++) {
int row = currentloc.back().first;
int column = currentloc.back().second.first;
int dirs = currentloc.back().second.second;

if (dirs == 0) {
currentloc.push_back(make_pair(row, make_pair(column + 1, dirs)));
column += 1;
}
else if (dirs == 1) {
currentloc.push_back(make_pair(row + 1, make_pair(column, dirs)));
row += 1;
}
else if (dirs == 2) {
currentloc.push_back(make_pair(row, make_pair(column-1, dirs)));
column -= 1;
}
else {
currentloc.push_back(make_pair(row-1, make_pair(column, dirs)));
row -= 1;
}
ans++;

if (row <= 0 || row> n || column <= 0 || column > n) 
return -1;
if (visited[row][column] != -1)
return -1;
visited[row][column] = dirs;
if (location[row][column] == 1) {
location[row][column] = 0;
}
else{
int x = currentloc.front().first;
int y = currentloc.front().second.first;
currentloc.pop_front();
visited[x][y] = -1;
}
}
if (dir == 'D') {
if (currentloc.back().second.second == 3)
currentloc.back().second.second = 0;
else
currentloc.back().second.second += 1;
}
else {
if (currentloc.back().second.second == 0)
currentloc.back().second.second = 3;
else
currentloc.back().second.second -= 1;
}
return 0;
}

int main(void) {
int move;
currentloc.push_back(make_pair(1,make_pair(1, 0)));
cin >> n >> applenum;

memset(location, 0, sizeof(location));
memset(visited, -1, sizeof(visited));
visited[1][1] = 0;
for (int i = 0; i < applenum; i++) {
int row, column;
cin >> row >> column;
location[row][column] = 1;
}
cin >> move;
int flag = 0;
for (int i = 0; i < move; i++) {
int counts;
char dir;
cin >> counts >> dir;
if (flag == 0){
if (dfs(counts, dir) == -1)
flag = 1;
}
}
if (flag == 0)
dfs(ans + n+1,0);
cout << ans;
return 0;
}