I submitted below codes for this problem.I got AC for one and TLE for other. I am unable to find how its happening. Please Help.
AC Submission
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int dx[] = {2, 2, -2, -2, 1, 1, -1, -1};
int dy[] = {1, -1, 1, -1, 2, -2, 2, -2};
bool isValid(int x, int y) {
return x >= 0 && x < 8 && y >= 0 && y < 8;
}
int bfs(int x1, int y1, int x2, int y2) {
vector<vector<bool>> vis(8, vector<bool>(8, false));
queue<pair<pair<int, int>, int>> q;
q.push({{x1, y1}, 0});
vis[x1][y1] = true;
while (!q.empty()) {
auto cur = q.front();
q.pop();
int x = cur.first.first;
int y = cur.first.second;
int dist = cur.second;
if (x == x2 && y == y2) {
return dist;
}
for (int i = 0; i < 8; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (isValid(nx, ny) && !vis[nx][ny]) {
vis[nx][ny] = true;
q.push({{nx, ny}, dist + 1});
}
}
}
return -1; // If no path exists
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
string start, end;
cin >> start >> end;
int x1 = start[0] - 'a';
int y1 = start[1] - '1';
int x2 = end[0] - 'a';
int y2 = end[1] - '1';
int ans = bfs(x1, y1, x2, y2);
cout << ans << endl;
}
return 0;
}
TLE Submission
#include<bits/stdc++.h>
using namespace std;
int ans;
void bfs(int x1, int y1, int x2, int y2)
{
vector<vector<bool>> vis(8, vector<bool> (8, 0));
queue<vector<int>> q;
q.push({x1,y1,0});
while(!q.empty())
{
vector<int>s = q.front();
q.pop();
vis[s[0]][s[1]] = 1;
if(s[0] == x2 && s[1] == y2)ans = min(ans, s[2]);
vector<vector<int>> v;
v.push_back({s[0]+2,s[1]-1,s[2]+1});
v.push_back({s[0]+2,s[1]+1,s[2]+1});
v.push_back({s[0]-2,s[1]-1,s[2]+1});
v.push_back({s[0]-2,s[1]+1,s[2]+1});
v.push_back({s[0]+1,s[1]-2,s[2]+1});
v.push_back({s[0]+1,s[1]+2,s[2]+1});
v.push_back({s[0]-1,s[1]-2,s[2]+1});
v.push_back({s[0]-1,s[1]+2,s[2]+1});
for(auto u : v)
{
if((u[0]>=0 && u[0]<=7 && u[1]>=0 && u[1]<=7) && !vis[u[0]][u[1]])
{
q.push(u);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
ans = INT_MAX;
string start,end;
cin>>start>>end;
int x1,y1,x2,y2;
x1 = start[0]-'a';
y1 = int(start[1]-'1');
x2 = end[0]-'a';
y2 = int(end[1]-'1');
bfs(x1,y1,x2,y2);
cout<<ans<<endl;
}
return 0;
}
-is-this-fft- Maybe you can help.
Anyone?
In your TLE submission, you are marking the cell as visited when it is in front of the queue, not when it is added.
Let's say you have $$$b3$$$ and $$$c2$$$ in your queue. You will be adding $$$a1$$$ twice as when $$$b3$$$ and $$$c2$$$ arrive in front of the queue, as $$$a1$$$ isn't marked as visited when added by $$$b3$$$, so it will be added again when it is $$$c2$$$'s turn.
This can go upto 8 for points which can be reached from 8 different points.