Can a Physics grad get hired as a programmer?

I graduated with a BS in physics and applied math from a reputable state school, but I only took 1 C++ course as an undergrad and completed just 1 physics project using C++.

I was recently hired by a game company for a software engineer position, but I was fired within 2 months. They told me that because they are a small company (about 10 employees), they couldn't afford to offer me training and had to terminate me. They suggested that I enroll in institutes/programs that teach programming skills to people like me.

Are they right? Or do I just need to study some more on my own, maybe for a few months and I can get a programming job?

How much better would I look if I enrolled in an Applied Math MS program? I'm open to working in data mining, AI, statistics, etc. I don't have to work only as a programmer